[Leetcode] 442. Find All Duplicates in an Array 문제풀이

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

Find All Duplicates in an Array - LeetCode

 

문제 내용

배열 중에 같은 수 찾기 문제

요소는 1개 또는 2개로 이루어져있다.

 

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]

Output: [2,3]

 

문제 풀이

시간복잡도 O(n), 공간복잡도 O(1) 만에 풀 수 있다.

 

배열의 특징을 자세히 살펴보면,

요소가 1부터 n까지 범위가 있고,

각 요소는 1개 또는 2개로 이루어져있다.

 

이 특징을 이용해서 배열의 값을 인덱스로 생각하는 방식으로 풀면된다.

각 배열의 값을 인덱스로 나열하다가 서로 겹치면 2개인 것이다.

 

그래서 값이 값으면 -1 해서 중복을 방지했고,

다르면 swap해서 해당 인덱스에 맞는 값을 배치했다.

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        
        int i = 0;
        while(i < nums.size()) {
            int j = nums[i]-1;
            
            if (nums[i] != -1 && i != j) {
                if (nums[i] == nums[j]) {
                    ans.push_back(nums[i]);
                    nums[i] = -1;
                    i++;
                } else {
                    swap(nums[i], nums[j]);
                }
            } else {
                i++;
            }
        }
        
        return ans;
    }
};

swap 없이 하면 더 빠르게 가능했다.

swap을 하는 이유는 인덱스를 표시하기 위함인데

방문했다는 표시로 음수를 주면 된다.

방문한 값이 음수면 이미 방문했다는 의미이다.

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