[Leetcode] 540. Single Element in a Sorted Array 문제풀이

https://leetcode.com/problems/single-element-in-a-sorted-array/

Single Element in a Sorted Array - LeetCode

 

문제 내용

정렬된 배열이 있다.

그리고 배열에는 2개씩 중복되는 숫자가 있다.

1개만 중복 안되는 숫자로 구성되어 있는데 이 숫자를 구하는 문제

 

Example 1:

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

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

 

문제 풀이

정렬되어 있는 배열에서 특정한 숫자를 찾는 알고리즘으로는 바이너리 서치가 있다.

하지만 문제에서는 단순 바이너리 서치가 아니라 중복 안되는 숫자를 찾는 문제이다.

바이너리 서치를 할 때는 필요한 것이

• 찾고자 하는 숫자
• 어떻게 비교

2가지를 찾아야 하는데 언뜻봐서는 보이지 않는다.

오히려 찾을 숫자가 우리가 원하는 return 값이다.

 

바이너리 서치를 할 때 중간을 찾아서 비교해서 위로 또는 아래로 갈지 정해야 되는데

중간값이랑 인접한 같은 값을 찾고,

index가 짝수인지 홀수인지 나눠서 찾을 수 있다.

예를 들어,

[1, 1, 2, 3, 3, 4, 4] 배열이 있으면

index 3을 찾으면 index 4와 같은 값을 갖게 된다.

그러면 위쪽은 다 짝이 있는 수만 있기 때문에 아래쪽으로 탐색하면 된다.

 

코드

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int s = 0;
        int e = nums.size()-1;
        int ans = nums[s];
        
        while(s < e) {
            int m = (s+e)>>1;
            
            if (s < m && nums[m] == nums[m-1]) {
                if (m%2) {
                    s = m+1;
                    ans = nums[s];
                } else {
                    e = m;
                }
            }
            else if (e > m && nums[m] == nums[m+1]) {
                if (m%2) {
                    e = m-1;
                    ans = nums[e];
                } else {
                    s = m;
                }
            }
            else {
                ans = nums[m];
                break;
            }
        }
        
        return ans;
    }
};