关关的刷题日记100 – Leetcode 442. Find All Duplicates in an Array- 专知

会员服务 ·

关关的刷题日记100 – Leetcode 442. Find All Duplicates in an Array

专知内容组（编）

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记100 – Leetcode 442. Find All Duplicates in an Array

题目

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:

[4,3,2,7,8,2,3,1]

Output:

[2,3]

题目的意思是给定一个长度为n的整数数组，数组中的元素1 ≤ a[i] ≤ n，有些元素出现一次，有些出现两次，让我们找出出现两次的元素。题目要求不开辟额外空间来实现时间复杂度O(n)的方法。

思路

之前做过类似的题目，时间复杂度O(n)，所以只能从头到尾遍历一次，不能做排序等操作。题目要求不能开辟额外空间，既然给定的数组中元素x都是介于1-n之间的，而数组正好也有n个元素，我们正好可以用a[x]的正负性来标记x是否出现过。

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int>re;
        for(int x:nums)
        {
            if(nums[abs(x)-1]<0)
                re.push_back(abs(x));
            else
                nums[abs(x)-1]*=-1;
        }
        return re;
    }
};