LeetCode 268 Missing Number

概述

https://leetcode.com/problems/missing-number/

布尔数组映射法

构造一个布尔数组，遍历一遍给定数组，标记布尔数组对应位置，之后再遍历一遍布尔数组即可。

O(n) 时间复杂度，O(n) 空间复杂度。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        vector<bool> exist(nums.size() + 1, false);
        for (auto n : nums) exist[n] = true;
        for (int i = 0; i < nums.size() + 1; i ++) {
            if (!exist[i]) return i;
        }
        return -1;
    }
};

求和法

笑死我们可以直接求和算出来目标值。

O(n) 时间复杂度，O(1) 空间复杂度。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int sum = 0;
        for (auto n : nums) sum += n;
        int t = nums.size() * (nums.size() + 1) / 2;
        return t - sum;
    }
};

其实可以边求和边减的。

位运算

1. 一个数和它本身做异或运算结果为 0，一个数和 0 做异或运算还是它本身。
2. 异或运算满足交换律和结合律。

所以直接所有有的值和所有索引（包括没有的值得那个索引）做异或，最终结果就是目标值。

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

Links: leetcode-268-missing-number

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