LeetCode442. Find All Duplicates in an Array解题

ゝ一世哀愁。 2022-06-05 07:28 90阅读 0赞

忙一点总比闲着好，是吧

# 先来看一下题目 #

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?

> 题目的大意是，给定一个整数的数组，里面的元素都在1和n之间（n是数组的长度）,里面有些元素会出现两次，其余的都只出现一次。你的任务是找到这个数组里面出现两次的元素  
> 另外要求只用O(n)的时间复杂度以及不需要用额外空间  
> *（这个额外空间的意思，我并没有弄太明白，一开始我以为是不能使用变量以及数组，但是我都用了，仍然AC了，有明白的可以留言告诉我一下么）*

Example:  
Input:  
\[4,3,2,7,8,2,3,1\]

Output:  
\[2,3\]

# 解题 #

这种寻找数组中冗余元素的题，目前我累计有两个方法：1.转换为负数进行标记 2.转换为下标的数进行交换，在这里我用第一种  
遍历数组，将元素对应位置的值转为负数，当再次遍历到这个元素时，就会发现对应的值是负的，说明这是个冗余的元素，将它加入结果数组中。  
只适宜出现重复两次的情况，重复出现三次就不能用这个方法了。

class Solution {
    public:
        vector<int> findDuplicates(vector<int>& nums) {
            int i,index;
            int length=nums.size();
            vector<int> result;
    
            for(i=0;i<length;i++){
                index=nums[i];
                if(index<0)
                    index*=-1;
                index--;
                if(nums[index]<0){
       //found the duplicate one
                    result.push_back(index+1);
                }else{
                    nums[index]*=-1;//mark corresponding element
                }
    
            }
              return result;
        }
    };

# 更好的算法 #

class Solution {
    public:
        vector<int> findDuplicates(vector<int>& nums) {
            vector<int> res;
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] != nums[nums[i] - 1]) {
                    swap(nums[i], nums[nums[i] - 1]);
                    --i;
                }
            }
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] != i + 1) res.push_back(nums[i]);
            }
            return res;
        }
    };

这是利用第二种，就是下表元素交换的方法