LeetCode题解之Find All Duplicates in an Array

1、题目描述

2、问题分析

将数组中的元素 A[i] 放到 A[ A[i] - 1] 的位置。然后遍历一边数组，如果不满足 A[i] == i+1，则将A[i]添加到 结果中。

3、代码

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