c++ leetcode array find duplicate by O(N)

배열 { 1,2,3,3,5,} 에서 중복을 찾는 것은 쉽다.

 

그렇지만 O(N)으로 중복을 찾으려면?

코드 >>

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
 
// Find Duplicates by O(N)
 
int FindDuplicates(std::vector<int>& nums)
{
    int k;
    for (int i = 0; i < nums.size(); i++)
    {
        k = nums[i];
        if (nums[k-1] >= 0)
            nums[k-1] = -nums[k-1];
        else
            return nums[i];
    }
    return -1;
}
 
 
int main()
{
    std::vector<int> nums = { 1,2,3,3,5,};
    int ans = FindDuplicates(nums);
    std::cout << ans << std::endl;
 
    return 0;
}