[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

Single Element in a Sorted Array - Medium

 

 

정렬 되어 있는 수로 이루어진 배열이 주어진다.

이 배열에 있는 수들은 한가지 수 빼고는 모두 두번씩 나온다.

이 때, 한번만 나오는 수를 구하는 문제다.

제한조건은 O(log n) 의 시간복잡도와 O(1)의 공간복잡도로 풀이를 해야한다.

 

제한조건이 없다면 처음부터 끝까지 배열을 탐색하면 되지만, 제한조건이 있으므로 방법을 달리해야한다.

다행히 제한조건을 보고 힌트를 얻을 수 있다.

O(log n)이라면 이진탐색을 사용하는 문제일 것이다.

이진 탐색이라면 공간역시 l,r,m 세 int 밖에 사용되지 않으므로 O(1) 이다.

l=0, r=nums.size()-1, m = (l+r)/2 로 설정을 하자.

이 떄, m이 나타내는 수를 M이라고 하자.

M이 두번 나오는 수라면, M의 앞이나 뒤에 M이 또 존재할 것이다.

최대한 M을 당겨줘보자. 

즉, m>0이고, nums[m-1]==nums[m] 이라면 m--를 해주자.

이렇게 해주면, M의 앞에 있는 수들이 모두 두번씩 나왔다면 0~m-1까지 (m개) 가 짝수여야한다.

 

홀수라면, 이 앞에 답이 있는 것이므로 r = m-1로 세팅해주자.

짝수라면, 이 뒤에 답이 있거나 M이 답이라는 것이다. 먼저 M이 답인지 체크해주자.

nums[m+1]==nums[m] 인지 확인하여 아니라면 바로 M을 리턴해주고,

맞다면 l = m+1로 세팅해주자.

 

마지막으로 m = (l+r)/2 로 다시 세팅해주고 돌려주자.

 

전체 풀이 코드

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l=0, r=nums.size()-1, m=(l+r)/2;
        while (l<r) {
            if (m && nums[m-1] == nums[m]) m--;
            if (m&1) r = m-1;
            else if (nums[m+1]==nums[m]) l=m+2;
            else return nums[m];
            m = (l+r)/2;
        }
        return nums[m];
    }
};