题目描述
统计一个数字在排序数组中出现的次数。
示例:
输入: nums = [5,7,7,8,8,10], target = 8 输出: 2
思路
1.排序数组中,相同的数字时连在一起的。
2.进行两次二分查找,分别查找目标数字的左边界索引和右边界索引,最后进行区间计算即可。
注:可以在第一次二分查找后,检查下该目标数字是否存在,可以有效减少无效操作
Java代码实现
public class Solution { public int GetNumberOfK(int[] nums, int target) { int leftIndex = -1; int rightIndex = -1; int left = 0; int right = nums.length-1; while(left <= right){ int mid = (left+right)/2; if(nums[mid] == target){ if(mid == 0 || nums[mid-1] != nums[mid]){ leftIndex = mid; break; }else{ right = mid - 1; } }else if(nums[mid] > target){ right = mid - 1; }else { left = mid + 1; } } if (leftIndex == -1){ return 0; } left = 0; right = nums.length - 1; while(left <= right){ int mid = (left+right)/2; if(nums[mid] == target){ if(mid == nums.length-1 || nums[mid+1] != nums[mid]){ rightIndex = mid; break; }else{ left = mid + 1; } }else if(nums[mid] > target){ right = mid - 1; }else { left = mid + 1; } } return rightIndex - leftIndex + 1; } }
Golang代码实现
func GetNumberOfK(nums []int, target int) int { leftIndex,rightIndex := -1,-1 left,right := 0,len(nums)-1 for left <= right{ mid := (left+right)/2 if nums[mid] == target { if mid == 0 || nums[mid-1] != nums[mid]{ leftIndex = mid break }else{ right = mid - 1 } }else if nums[mid] > target{ right = mid -1 }else{ left = mid + 1 } } if leftIndex == -1 { return 0 } left,right = 0,len(nums)-1 for left <= right{ mid := (left+right)/2 if nums[mid] == target { if mid == len(nums)-1 || nums[mid+1] != nums[mid]{ rightIndex = mid break }else{ left = mid + 1 } }else if nums[mid] > target{ right = mid -1 }else{ left = mid + 1 } } return rightIndex- leftIndex + 1 }