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

2021-03-21 19:27

阅读：694

标签：大于 abs numbers 观察负数 public info 因此线性时间

技术图片

题目要求只能用常数空间和线性时间完成这个任务，因此需要用一个比较取巧的做法。

在没有空间限制的情况下，我们会想到对每个值做一个映射，比如用一个哈希表计算每个数出现的次数。但是由于此题对空间进行了限制，
因此我们只能在原数组上进行“映射”，再由观察发现，每个数的值都是1～n内的整数，正好可以将值映射到下标。

所以可以这样：对于一个值nums[i],我们将nums[nums[i]]变为负数，这样，一遍扫描之后。再进行第二遍扫描。如果某个数j未在数组中出现过，这nums[j - 1]为正数。

代码如下：

class Solution {
public:
    vector findDisappearedNumbers(vector& nums) {
        int n = nums.size();
        for(int i = 0; i  0) {                        // 如果nums[pos]大于0，将它改为负数
                nums[pos] = -nums[pos];
            }
        }
        vector res;
        for(int i = 0; i  0) {                        // 如果nums[i]是正数，说明原数组不存在i + 1，因为如果存在i + 1,那么nums[i]在第一遍扫描的时候会被修改为负数
                res.push_back(i + 1);
            }
        }
        return res;
    }
};

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

标签：大于 abs numbers 观察负数 public info 因此线性时间

原文地址：https://www.cnblogs.com/linrj/p/13884559.html

上一篇：【Python】tesseract+uiautomator2+夜神模拟器悠长假期手游集市识别验证码自动购买

下一篇：程序员不愿意说的秘密！Java进阶架构师必看：架构完美设计+程序员三门课+架构修炼之道

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：LeetCode448. 找到所有数组中消失的数字
文章链接：http://soscw.com/index.php/essay/67297.html

亲，登录后才可以留言！

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

评论

热门文章

推荐文章

最新文章

置顶文章