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

传送门

leetcode

题目描述

一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0～n-1。
在范围 0～n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

C++ 代码 - leetcode

/*
    二分查找

    时间复杂度：O(logn)
*/
class Solution {
public:
    int takeAttendance(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] == mid) {
                l = mid + 1; // // [l, mid] 没有缺失任何数
            } else {
                r = mid; // 缺失的数在 [l, mid] 区间
            }
        }

        if (l == nums.size() - 1 && nums[l] == l) {
            l ++; // 缺失的数不在 [nums[0], nums[nums.size() - 1]] 范围内
        }
        
        return l;
    }
};

/*
    0～n-1 求和，遍历时减去 nums[i]

    时间复杂度：O(n)
*/
class Solution {
public:
    int takeAttendance(vector<int>& nums) {
        int n = nums.size() + 1;
        int sum = 0;
        for (int i = 0; i < n; i ++) sum += i;
        for (int i = 0; i < nums.size(); i ++) sum -= nums[i];
        
        return sum;
    }
};