LeetCode448 找到所有数组中消失的数字

发表于 | 分类于 |
字数统计: 392 | 阅读时长 ≈ 1

链接: https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/

题意

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

字节AILAB二面，当时没想到O(n)复杂度的算法，然后发现这道题以前做过
看来还是要多复习以前做过的题啊
不然做了忘=没做

解法

在面试的时候，我只能想到排序二分或者排序然后从前往后扫的做法
面试官要求是O(n)时间复杂度
没想出来

其实可以利用索引来做一个映射，对于数组的每个元素，把它对应下标的值标记为一个负数
然后再扫一遍看哪些是正数就是结果了
但是这个标记不能简单的标记为-1，因为会丢失原先的值，比如当前数字a对应的值是7，如果改成-1
7这个信息就会被丢失
一个巧妙的做法是把这个数改成原来的相反数，这样既保留了原先的信息，同时也可以标记
确实很难想到啊

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++)
        {
            nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1]);
        }
        vector<int> ret;
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] > 0) 
            {
                ret.push_back(i + 1);
            }
        }
        return ret;
    }
};