[leetcode]: 448. Find All Numbers Disappeared in an Array

古城微笑少年丶 2022-06-16 01:20 177阅读 0赞

**1.题目描述**  
Given an array of integers where 1 ≤ a\[i\] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of \[1, n\] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.  
翻译：给定一个数组a,其中1 ≤ a\[i\] ≤ n (n =数组长度)。找出其中没有出现的数字。  
要求：不使用额外空间，时间复杂度O(n)

**2.分析**  
需要两次遍历O(n)  
第一次遍历：标记出现过的数字  
第二次遍历：把没有标记的数字放入结果

不开辟额外空间：把标记直接做在原数组上就行。

**3.代码**

class Solution {
    public:
        vector<int> findDisappearedNumbers(vector<int>& nums) {
            for (int n : nums)
            {
                int index = abs(n) - 1;//把该数字对应index处的值变为负数，作为标记
                nums[index] = nums[index] > 0 ? -nums[index] : nums[index];
            }
            vector<int> result;
            for (int i = 0; i < nums.size(); i++)
                if (nums[i] > 0)
                    result.push_back(i + 1);
            return result;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，177人围观）

还没有评论，来说两句吧...

相关阅读

相关 448. Find All Numbers Disappeared in an Array(1-n未出现的数)

给定整数的数组，其中1≤A \[1\]≤ Ñ（Ñ =数组的大小），一些元件出现两次以及其他出现一次。查找\[1，n \]包含的所有未出现在此数组中的元素。您可以在没

客官°小女子只卖身不卖艺/ 2023年07月25日 12:35/ 0 赞/ 11 阅读

相关【Leetcode】448. Find All Numbers Disappeared in an Array

思路：用标志位的方法去做，把原数组中出现的数应该在的位置上的数置为负值，然后重新遍历如果大于0，说明未置为负值过，也就是表示从未出现过。 public cl

谁借莪１个温暖的怀抱￠/ 2022年09月29日 06:10/ 0 赞/ 178 阅读

相关 leetcode之Find All Numbers Disappeared in an Array

问题来源：[Find All Numbers Disappeared in an Array][] 很久没有刷题了，感觉大脑开始迟钝，所以决定重拾刷题的乐趣。一开始不要太难

╰+哭是因爲堅強的太久メ/ 2022年07月13日 04:23/ 0 赞/ 68 阅读

相关 [leetcode]: 448. Find All Numbers Disappeared in an Array

1.题目描述 Given an array of integers where 1 ≤ a\[i\] ≤ n (n = size of array), some eleme

古城微笑少年丶/ 2022年06月16日 01:20/ 0 赞/ 178 阅读

相关 LeetCode448. Find All Numbers Disappeared in an Array 解答

现在才发现每次提交的时候runtime是不同的，可能这一次提交的runtime是20ms，但是下一次提交的runtime就是18ms了，所以以后还是老老实实用时间复杂度来衡量吧

矫情吗；*/ 2022年06月07日 08:44/ 0 赞/ 170 阅读

相关 448. Find All Numbers Disappeared in an Array

[原题链接][Link 1] 这个题主要是寻找没有出现的数字。代码的主要思路是，如果找到数值i，则把对应i-1索引的值取负。之后遍历列表，如果发现i-1里面的数>

秒速五厘米/ 2022年06月02日 09:22/ 0 赞/ 176 阅读

相关 448. Find All Numbers Disappeared in an Array

> Given an array of integers where 1 ≤ a\[i\] ≤ n (n = size of array), > some elements

Love The Way You Lie/ 2022年06月01日 00:23/ 0 赞/ 221 阅读

相关 448. Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a\[i\] ≤ n (n = size of array), some elements appea

r囧r小猫/ 2021年10月01日 07:30/ 0 赞/ 233 阅读

相关【LeetCode Top 100】448. Find All Numbers Disappeared in an Array【Easy】【JAVA】

1. 题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9n

阳光穿透心脏的1/2处/ 2021年09月21日 00:58/ 0 赞/ 243 阅读

相关 LeetCode : 448. Find All Numbers Disappeared in an Array 数组中的缺失数

试题 Given an array of integers where 1 ≤ a\[i\] ≤ n (n = size of array), some elements

港控/mmm°/ 2021年06月24日 16:11/ 0 赞/ 292 阅读