Find the Duplicate Number

좀 새로운 문제 유형이다. 일단 이 문제는 배열안에 있는 원소는 변경하면 안되고 다른 자료구조를 사용하면 안되는 문제다.

그렇기 때문에 Map이나 Sorting이 안되기 때문에 어떻게 풀어야 고민하던 와중에 이분탐색 문제 유형이란것을 보고 답을 참고하면서 고민했다.

반복이 되는 숫자는 단 하나 뿐이며, 룹을 두번 돌리면서 찾을 수는 없기에 중간 지점을 먼저 뽑는다.

이후에는 그 숫자로 원본 배열을 탐색해서 작거나 같은 숫자를 확인했을때 더 크다면? 중복된 숫자가 하나 이상 발생했던기 때문에 탐색 범위롤 좁혀가면서 찾아야 한다.

만약에 정상 범주면은 mid 를 올려줌으로서 탐색 범위를 조정한다.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = 1, high = nums.size(); 
        int duplicate = -1; 
        while(low <= high){
            int mid = (low + high) / 2; 
            int count = 0; 
            for(int& n : nums){
                if(n <= mid) count++;  
            }

            if(count <= mid){ //정상적인 숫자일 때 
                low = mid + 1;  
            } else{
                duplicate = mid; 
                high = mid - 1; 
            }
        }

        return duplicate; 

    }
};