Leetcode <Binary Search> 287. Find the Duplicate Number 53.1% Medium

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

 

배열에는 중복된 수가 무조건 존재하고 이 수를 찾기

 

Example 1:

Input: [1,3,4,2,2]

Output: 2

 

Example 2:

Input: [3,1,3,4,2]

Output: 3

 

Note:

1. You must not modify the array (assume the array is read only). // 배열 고칠 수 없음
2. You must use only constant, O(1) extra space. //정수만 사용가능
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once. // 배열에는 중복된 번호가 한 개뿐이지만 두 번 이상 반복될 수 있다. 

----------------------------------------------------------------------------------------------------------------------

이거 풀 수 있을 것같아서 했는데 못함,, 솔루션 보니깐 한 끗 차이,, ,,,,,,,,,,

 

int nums[] = {2,1,0,3,1};  // 근데 위에서 배열 read only 라 해서 정렬 안해준건데 뭐지..?

 

Arrays.sort(nums);        // 여기서 먼저 오름차순으로 배열 정렬해주면, {0,1,1,2,3} 이렇게 되고 같은 수는 무조건 같이                                   //붙어있으니깐 바로 옆에 있는 수만 비교해 주면 된다. 

 

   for(int i=1; i<nums.length ;i++) {

    if(nums[i] == nums[i-1]){     // 이렇게 하면 nums[1] == nums[0]

                                                            nums[2] == nums[1]

                                                            nums[3] == nums[2]

                                                            nums[4] == nums[3]

                                                           
     System.out.println(nums[i]);
 }

}