剑指Offer-面试题53-I-在排序数组中查找数字I

题目描述

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

示例1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

限制：0 <= 数组长度 <= 50000

思路

由于是排序数组，因此使用二分法来查找target，如果找到了，就往这个数的左边和右边进行遍历，找相同的，统计个数。如果没找到，则返回0。

代码

class Solution {
    public int search(int[] nums, int target) {
        //数组为空处理
        if(nums == null || nums.length == 0){
            return 0;
        }
        int left = 0;   //左指针
        int right = nums.length - 1;    //右指针
        int mid = 0;    //中间指针
        int count = 0;  //次数统计
        //二分法查找
        while(left <= right){
            mid = (left + right) / 2;
            if(nums[mid] == target){    //=说明找到，count+1，并退出查找
                count++;
                break;
            }
            else if(nums[mid] < target){    //<说明在右半部分
                left = mid + 1;
            }
            else{
                right = mid - 1;    //>说明在左半部分
            }
        }
        if(count == 0){ //如果没找到，返回0
            return 0;
        }
        else{   //找到了，就往左往右遍历统计个数
            left = mid - 1;
            right = mid + 1;
            while(left >= 0 && nums[left] == target){
                left--;
                count++;
            }
            while(right < nums.length && nums[right] == target){
                right++;
                count++;
            }
            return count;
        }
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。