Cinte's Leetcode Record
0%

剑指 Offer 53 - II. 0～n-1中缺失的数字

Posted on Edited on In Disqus:
Symbols count in article: 523 Reading time ≈ 1 mins.

剑指 Offer 53 - II. 0～n-1中缺失的数字

遍历
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; ++i)
            if(nums[i] != i)
                return i;
        return n;
    }
};

排序数组中的搜索问题，首先想到 二分法 解决。

二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int lo = 0, hi = n; // 这里hi不能是n-1，当所有数字全在范围内时，hi不会改变，这样一来lo会像hi靠近，这样返回的hi还是n，符合结果
        while(lo < hi)
        {
            int mid = lo + ((hi - lo) >> 1);
            if(nums[mid] != mid)
                hi = mid;
            else
                lo = mid + 1;
        }
        return hi;
    }
};