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

﹏ヽ暗。殇╰゛Y 2022-09-08 03:46 126阅读 0赞

> 统计一个数字在排序数组中出现的次数。
> 
> 示例 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
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
        public int search(int[] nums, int target) {
            int i = 0,j = nums.length-1;
            int m = (i + j) / 2;
            // 一直向右找到右边界，不包括target的值
            while(i <= j){
                if(nums[m] <= target) { i = m + 1; }
                else { j = m - 1; }
                m = (i + j)/2;
            }
            int right = i;
            i = 0;
            j = nums.length - 1;
            m = (i + j) / 2;
            // 一直向左找到左边界，不包括target的值
            while(i <= j){
                if(nums[m] >= target) { j = m-1;}
                else { i = m + 1; }
                m = (i + j)/2;
            }
            int left = j;
            return right - left - 1;
        
        }
    }

>     while(i <= j){
>            if(nums[m] <= target) { i = m + 1; }
>            else { j = m - 1; }
>            m = (i + j)/2;
>        }
>        int right = i;
> 
> 因为不知道target的值到底存在多少，所以使用二分法查找对应值。
> 
> 循环开始的时候，i为0，j为数组最后一位length-1。
> 
> ① 当nums\[m\] 的值小于target的时候，由题目知数组为非递减数组，说明target的值还在nums\[m\]后面
> 
> 所以i = m + 1，然后再次计算m的值。
> 
> ② 当nums\[m\]的值等于 target 的时候，由题目知数组为非递减数组，说明target值在nums\[m\]之前或者之后，那么右边界肯定在nums\[m\]的右边了，所以还是 i = m + 1，然后再次计算m的值。
> 
> ③ 当nums\[m\]大于target的时候，这个时候右边界在nums\[m\]或者其左边，所以 j = m-1。
> 
> ④ 当i > j 的时候，i从左往右一直往右边靠，越过了所有target的值，j从右往左，两者已经碰面过了，说明此时已经找到了右边界，跳出循环，此时 i 的值为右边界的值。

找左边界同理。

不要花大量的时间去做容易的环节，如同健身锻炼，如果你每天锻炼身体，锻炼完一点不累，那就说明没有锻炼到位，没什么作用。

学习也是一样，一直待在舒适区里，就没办法进入到提升区。

去完成那些需要深入思考，需要克服困难才能完成的任务，这样才能一点一点成长。当然也不要给自己设置过于困难的任务，不然容易让自己陷入负面学习的情绪中，踮踮脚蹦一蹦能够到的最好。