文章目录

1.题目2.思路3.代码

1.题目

统计一个数字在排序数组中的出现的次数。

2.思路

解法一：从头到尾遍历，时间复杂度为O（n）。 解法二：考虑数组为空的情况，直接返回0；双指针，找到i和j的位置，时间复杂度为O（n/2）。 解法三：二分查找算法。 我 们意识到，数字出现的次数=index（最后一个）-index（第一个）+1. 因此可以采用二分查找算法找到第一个和最后一个重复数字出现的位置。 先拿数组中间的数字和要统计的目标值k作比较： 若data[mid]>k，k只可能出现再数组的前半段； 若data[mid]<k，k只可能出现在数组的后半段； 若data[mid]==k，需要判断这个k是不是第一个。有两种情况，若中间数字的前一个不是k，则中间数字就是第一个k；若前一个也是k，那么第一个k肯定在数组的前半段，下一轮需要在数组的前半段查找。 同理，同样的思路查找最后一个k的位置。

3.代码

解法一：

# -*- coding:utf-8 -*- class Solution: def GetNumberOfK(self, data, k): # write code here count = 0 for i in data: if k==i: count+=1 return count

解法二：

class Solution: def GetNumberOfK(self, data, k): if len(data) == 0: return 0 i = 0 j = len(data) - 1 while i < j and data[i] != data[j]: if data[i] < k: i += 1 if data[j] > k: j -= 1 if data[i] != k: return 0 return j-i+1

解法三：二分查找法

# -*- coding:utf-8 -*- class Solution: def GetNumberOfK(self, data, k): # write code here def binarysearch(nums, target, left): low = 0 high = len(nums) - 1 while low <= high: mid = low + (high-low) // 2 if nums[mid] == target: if left: high = mid-1 else: low = mid+1 elif nums[mid] > target: high = mid - 1 else: low = mid + 1 if left: if (low>=len(nums) or nums[low]!=target): return -1 else: return low else: if (high<0 or nums[high]!=target): return -1 else: return high if not data: return 0 return binarysearch(data, k, 0) - binarysearch(data, k, 1) + 1 if binarysearch(data, k, 0)>=0 else 0