287. Find the Duplicate Number c++ 문제 풀이

각 정수가 [1, n] 범위 내에 있는 n + 1 정수를 포함하는 정수 배열을 지정합니다.
숫자로 반복되는 숫자가 하나뿐입니다. 이 반복된 숫자를 반환합니다.
배열 번호를 수정하지 않고 일정한 추가 공간만 사용하여 문제를 해결해야 합니다.

Medium 난이도

 

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

 

Constraints:

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

 

Follow up:

• 적어도 하나의 중복 번호가 숫자로 존재해야 한다는 것을 어떻게 증명할 수 있습니까?
• 선형 런타임 복잡도에서 문제를 해결할 수 있습니까?

o(n log n)

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        
        for(int i = 0 ; i < nums.size(); ++i){
            
            if(nums[i]==nums[i+1]) return nums[i];
        }
    return 0;
    }
};

o(nlog n ) 으로 풀면 상당히 쉬운 문제이다. 

 

이문제가 Medium  난이도를 가지는 것은 o(n) timecomplexity로 풀며 공간복잡도(1) 을 사용할때라고 한다.

 

이 방식으로 풀기위해서 새로운 접근 법이 필요하다. 

nums가 이미 가지고 있는 nums에 표식을 새기는 것이다.

nums에 인자에 -를 붙혀주는 방식으로 할 수 있다.

 

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int duplicate = -1;
        for (int i = 0; i < nums.size(); i++) {
            int cur = abs(nums[i]);
            if (nums[cur] < 0) {
                duplicate = cur;
                break;
            }
            nums[cur] *= -1;
        }

        return duplicate;
    }
};

cur를 abs로 절댓값으로 만들어 배열의 인자의 크기를 벗어나는 경우를 막을 수 있다.

 

만약 nums에 이미 -인 값이 있다면 그 같은 중복된 수이므로 반복문을 탈출하고 duplicate를 리턴하게 된다.

 

운영중인 카톡방입니다.

https://open.kakao.com/o/gsMhUFie

C/C++/C# 언리얼/유니티 /질문