欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode之Find All Duplicates in an Array

程序员文章站 2022-07-15 13:05:50
...

本题的意思是给定一个整数数组,其中每个元素x都满足1 <= x <= n,其中n是该数组的元素数量。该数组中每个元素要么出现1次,要么出现2次。要求在不使用额外空间和在O(n)的时间复杂度内的条件下,找出所有出现2次的元素。

本题解法:从头至尾遍历该数组,将数组下标为当前访问的数组元素值减一的元素置为其本身的相反数(如果其本身现在是正数),那么如果以后再访问到与当前元素相同的元素,就会发现数组下标为当前访问的数组元素值减一的元素已经是负数了,就可以将这个当前访问的元素挑选出来,遍历完后,即可挑选出所有出现2次的元素。

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

LeetCode之Find All Duplicates in an Array