C++ 287. Find the Duplicate Number(Leet Code)

Leet Code_287. Find the Duplicate Number

 

 

https://leetcode.com/problems/find-the-duplicate-number/

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

배열안의 중복된 숫자 찾기

​

방법

1. 배열안의 중복된 숫자 찾기

 

결과

배열안의 중복된 숫자 찾기

 

통과한 코드

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        std::map<int, int> m;
        std::map<int, int>::iterator it;
    
        for(int i = 0 ; i < nums.size() ; i++)
        {
            it =  m.find(nums[i]);
            if (it == m.end())
            {
                m.insert ( std::pair<int,int>(nums[i], 1) );
            }
            else
                return nums[i];
        }
        return 0;
    }
};

중복된 숫자를 찾기 위하여 map 자료구조를 사용하였다.

배열 값을 key로 사용하였다.

key를 find하여 없으면 새로 key, value를 생성하고 있으면 중복된 값이기 때문에 return 하여 해결하였다.

 

다른 사람은 어떻게 풀었는지 더 좋은 방법이 있는지 찾아보니 아래와 같은 코드가 있었다.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int dup=0;
        for(auto i:nums)
        {
            if(nums[abs(i)-1]<0)
            {
                dup=abs(i);
                break;
            }
            else
            {
                nums[abs(i)-1]=-nums[abs(i)-1];
            }
        }
        return dup;
    }
};

배열 값의 위치를 음수 값으로 바꿔서 음수면 return 하도록 짰다.

문제에 배열 값을 바꾸지 말라그랬는데 뭥미