[LeetCode] 442. Find All Duplicates in an Array

https://leetcode.com/problems/find-all-duplicates-in-an-array/description/

Leetcode - Find All Duplicaties in an Array

문제 유형 : 배열, 구현, 연결리스트

문제 난이도 : Medium

 

문제

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

 

n의 길이를 가진 정수 배열 nums가 주어집니다. nums의 값의 범위는 1 ~ n입니다.

각 정수는 1개 또는 2개씩 들어있습니다. 두 번 등장하는 정수들을 반환하시오.

 

O(n)에 끝내고, 상수 공간을 사용해야 합니다.

 

풀이

애초에 배열을 만들어서 반환해야 하므로, 최대 O(k) (k = n/2)내의 공간을 만들어야 합니다.

배열을 순차적으로 순회하면서, 다음의 과정을 거칩니다:

만약, nums[nums[i]]가 음수라면, 이미 한번 발견한 것으로 간주하고, 정답 배열에 넣습니다.

아니라면, nums[nums[i]]를 음수로 만듭니다. 이러면 다음에 발견될 때, 한번 발견된 배열임을 알 수 있습니다.

 

정답 배열을 반환합니다.

 

코드

C++

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