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

关关的刷题日记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;
    }
};

人生易老，唯有陪伴最长情，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。