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

概述

https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/

暴力遍历

注意默认值是 nums.size()。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] != i) return i;
        }
        return nums.size();
    }
};

求和法

求和直接算出缺失的值。

借鉴二分查找思想

找个短例子亲自过一小就好了。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (nums[m] == m) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        if (l == nums.size() - 1 && nums[l] == l) return nums.size();
        return l;
    }
};

另一种写法，此时我们需要检查当前值是否是目标值：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == m) {
                l = m + 1;
            } else {
                if (m != 0 && nums[m-1] == m - 1) return m;
                r = m - 1;
            }
        }
        return l;  // otherwise l will be push to the leftmost
    }
};

Links: sword-offer-53-2

未经允许，禁止转载，本文源站链接：https://iamazing.cn/