LeetCode 268 Missing Number

标签: 数学类题目 LeetCode 发布于:2022-02-24 22:41:37 编辑于:2022-02-24 22:54:09 浏览量:372

概述

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;
    }
};

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