数字在排序数组中出现的次数

题目描述

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

示例：

输入: 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
}