力扣---剑指 Offer 53 - I. 在排序数组中查找数字 I

标签：right 边界 nums int Offer mid 53 --- target

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

示例 1:

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

示例 2:

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

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

---

由于已经排好序了，很容易就能先到用二分查找。

普通思路是先二分查找找到一个符合要求的位置，然后从这个位置向两边遍历，同时计数，遇到不符合要求的数为止。

进阶的思路是用二分查找分别找到相同数的左边界和右边界，然后用右边界减去左边界的下标即可。

普通思路：

class Solution {
    public int search(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = (left + right) / 2;
        while (left < right) {
            if (nums[mid] == target) {
                break;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            mid = (left + right) / 2;
        }
        int res = -1;
        for (int i = mid; i >= 0; i --) {
            if (nums[i] == target) {
                res ++;
            } else {
                break;
            }
        }
        for (int i = mid; i < nums.length; i ++) {
            if (nums[i] == target) {
                res ++;
            } else {
                break;
            }
        }
        return res == -1 ? 0 : res;
    }
}

 

 进阶思路：

两种，一种是修改判断条件，二分查找两次，分别找到左边界和右边界。

另一种是进行一次二分查找，用两个变量来存储上一次的左边界和右边界，最后直接在上一次的左边界和mid，上一次的右边界和mid中分别查找左边界和右边界。

class Solution {     public int search(int[] nums, int target) {         if (nums.length == 0) {             return 0;         }         // 左边界         int left = 0;         // 右边界         int right = nums.length - 1;         // 上一次的左边界，最后可以直接在left1和left中间寻找第一次出现target的左边界         int left1 = left;         // 上一次的右边界，最后可以直接在right和right1中间寻找最后一次出现target的右边界。         int right1 = right;         int mid = (left + right) / 2;         while (left <= right) {             if (nums[mid] == target) {                 // 存在target，从上一次的左边界和上一次的右边界开始判断。                 left = mid;                 right = mid;                 // 寻找第一次出现target的左边界                 while (left1 < left) {                     mid = (left + left1) / 2;                     // 当前区间只存在两种数，小于target的数和等于target的数。                     if (nums[mid] == target) {                         left = mid - 1;                         // 避免越界和死循环。                         if (left < 0 || nums[left] != target) {                             left ++;                             break;                         }                     } else {                         left1 = mid + 1;                     }                 }                 // 寻找最后一次出现target的右边界。                 while (right < right1) {                     mid = (right + right1) / 2;                     // 当前区间只存在两种数，大于target的数和等于target的数                     if (nums[mid] == target) {                         right = mid + 1;                         // 避免越界和死循环。                         if (right >= nums.length || nums[right] != target) {                             right --;                             break;                         }                     } else {                         right1 = mid - 1;                     }                 }                 return right - left + 1;             } else if (nums[mid] < target) {                 left1 = left;                 left = mid + 1;             } else {                 right1 = right;                 right = mid - 1;             }             mid = (left + right) / 2;         }         // nums数组中不存在等于target的数。         return 0;     } }

 

 

标签：right,边界,nums,int,Offer,mid,53,---,target
From： https://www.cnblogs.com/allWu/p/17237509.html