LeetCode 面试题 17.19

发表于 更新于 分类于 阅读次数：

题目链接：LeetCode 面试题 17.19 - 消失的两个数字

这个题还蛮有意思的，题目限定了时间复杂度要\(O(n)\)，空间复杂度要\(O(1)\)，主要是空间限制。

对于 \(O(n)\) 的时间复杂度很容易想到哈希表，可是这需要额外的空间，即空间复杂度也是 \(O(n)\) 的。如何在不增加额外空间的前提下建立哈希表呢？我们知道所有的数都小 \(3\times 10^4\)，所以只需要在原数组上打标记就可以了，即读到一个实际值为 \(x\) 的数字，就在 \(x\) 的下标的那个数字上加上一个大于 \(3\times 10^4\) 的数字，或者把一个用不到的二进制位置 \(1\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    static constexpr int flag = int(1e5);

    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;
        int s = nums.size();
        for (int i = 1; i <= 3; ++i) {
            nums.push_back(0);
        }
        for (int i = 0; i < s; ++i) {
            if (nums[i] < flag) {
                nums[nums[i]] += flag;
            } else {
                nums[nums[i] - flag] += flag;
            }
        }
        vector <int> ret;
        for (int i = 1; i <= n; ++i) {
            if (nums[i] < flag) {
                ret.push_back(i);
            }
        }
        return ret;
    }
};