剑指Offer-第4天 查找算法（简单）

第一题

题目链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

个人题解：索引法

  1. 我们可以将数字和下表进行对应，每次把索引和下标一样的数字记录（强行变成）
  2. 当我们再次遍历的时候如果下标一样，就一定会有重复，返回其中一个即可。

代码：

class Solution {
public:
    int findRepeatNumber(vector& nums) {
        int i=0,n=nums.size();
        while(i

结果：

第二题

题目链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/ （其实挺好奇为什么他的题目的英文描述是拼音hhh）

个人题解：二分查找即可，时间复杂度 \(O(logN)\) (可以调用函数也可以手写)

代码：


class Solution {
public:
    int search(vector& nums, int target) {
        return upper_bound(nums.begin(), nums.end(), target) 
             - lower_bound(nums.begin(), nums.end(), target);
    }
};

class Solution {
public:
    int search(vector& nums, int target) {
        if(!nums.size()) return 0;

        int le=0,ri=nums.size()-1;
        while(le>1;
            if(nums[mid]>=target) ri=mid;
            else le=mid+1;
        }

        if(nums[ri]!=target) return 0;

        int idx=le;

        le=0,ri=nums.size()-1;
        while(le>1;
            if(nums[mid]<=target) le=mid;
            else ri=mid-1;
        }

        int idx1=ri;

        return idx1-idx+1;
    }
};

结果：(第一张图调用函数，第二张图手写，手写快了一点)

第三题

题目链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/

个人题解：二分查找，如果数字和下标一样则继续，反之退出

代码：

class Solution {
public:
    int missingNumber(vector& nums) {
        int i=0,j=nums.size()-1;
        while(i<=j){
            int mid=i+j>>1;
            if(nums[mid]==mid) i=mid+1;
            else j=mid-1;
        }
        return i;
    }
};

结果：

复刷剑指Offer

相关

标签