[008]Find All Duplicates in an Array

 

문제: https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3414/

---

 

주어지는 nums 배열을 hashMap처럼 사용하면 됩니다. 

 

아래 두 가지 조건 때문에 가능한데요.

1. 주어지는 모든 수가 배열의 인덱스 번호 이하의 숫자.

2. 양수라는 조건.

 

Single Number와 Duplicate Number의 차이점을 방문 표시 여부로 생각하면 됩니다.

특정한 nums[i] 값을 visited[] 배열에서의 index로 보게 되면, (int index = nums[i])

 

1. nums[i] 값이 나오면 해당 인덱스 숫자 nums[nums[i]] (== nums[index])를 음수로 만듭니다.

2. 배열을 순회 중 음수인 값의 인덱스를 만나게 되면, 이미 이 숫자는 사용되었던 숫자 임을 알 수 있습니다.

즉, 그 숫자가 Duplicate Number입니다.

 

막상 문제 풀 때 헷갈릴 수 있는 부분이 2가지가 있는데요.

1. 방문표시를 음수로 하기 때문에, 항상 절댓값으로 인덱스를 가져와야 Runtime Error를 피할 수 있습니다.

2. 문제 조건이 1 <= number <= nums.size() 이므로 적절히 -1을 취해서 Runtime Error를 피해야 합니다.

 

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