通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

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

63人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/879

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 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

难度:简单;标签:数组,二分查找;编程语言:C++


我的解法

class Solution {
public:
    //c++重写,logn复杂度
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, mid = -1;
        
        if(nums.size() == 0){
            return 0;
        }
        
        while(right >= left){
            mid = (right + left) / 2;
            if(nums[mid] == target){
                break;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        
        int left2, right2, mid2 = -1;
        if(nums[mid] == target){
            right2 = right;
            left2 = mid;
            right = mid;
            
            while(right2 >= left2){
                mid2 = (right2 + left2) / 2;
                if(nums[mid2] > target){
                    right2 = mid2 - 1;
                }else{
                    left2 = mid2 + 1;
                }
            }
            
            while(right >= left){
                mid = (right + left) / 2;
                if(nums[mid] < target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }else{
            return 0;
        }
        
        return (nums[mid2] > target ? mid2 - 1 : mid2) - (nums[mid] < target ? mid + 1 : mid) + 1;
    }
};

这里先二分查找找到一个target的位置,然后这个target位置的左右可能还有值为target的数,再左右二分查找target,最后mid, mid2就在target值的左,右边界附近了,注意return值要处理一下


其它解法

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int i=0, j=nums.size()-1;
        while(i<j){
            int mididx = (i+j)/2;
            //printf("%d,%d,%d\n", i, j, mididx);
            int midnum = nums[mididx];
            if(midnum > target){
                if(mididx == j){
                    j-=1;
                    continue;
                }
                j = mididx;
            }else if(midnum < target){
                if(mididx == i){
                    i+=1;
                    continue;
                }
                i = mididx;
            }else if(nums[i] < target){
                i++;
            }else if(nums[j]>target){
                j--;
            }else{
                break;
            }
        }
        //printf("i:%d,j:%d\n", i, j);
        if(j==i && nums[i]!=target)
        {
            return 0;
        }
        int ret = j-i+1;
        return ret;
    }
};

上面的意思是先二分找值为target的数,找到后左右指针每次+1,-1(不再二分)向找到的值target的数靠近,直到左,右(i, j)位置的数值都是target,如果中间有数不为target,再次二分,为target,再+1, -1,如此反复


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告