LeetCode442. Find All Duplicates in an Array解题

vincentbbli

发布于 2021-08-18 15:38:15

3010

发布于 2021-08-18 15:38:15

文章被收录于专栏：vincent随笔

忙一点总比闲着好，是吧

先来看一下题目

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;iif(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;
    }
};

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017/11/21 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度