[python3] 540. Single Element in a Sorted Array

풀이 일자: 23.02.21

난이도: [Medium]

분류: [Binary Search]

문제 내용

nums라는 배열 안에 여러 개의 숫자가 2번씩 나타나는 데 그 중 한번만 등장한 숫자를 리턴하는 문제이다.

logN의 시간복잡도와 O(1)의 공간복잡도를 가져야 한다.

 

문제 해결 흐름

1. 시간복잡도와 공간복잡도 제약 사항의 의미를 먼저 파악하자.

→ logN의 시간복잡도는 이진탐색을 사용하라는 것이고 O(1)의 공간복잡도는 다른 자료구조를 사용하지 않고 변수 몇개만 사용하라는 의미이다.

 

2. 이진탐색으로 하는 건 확인했고 그럼 1개만 있는 수의 위치를 알아야 이진탐색을 할텐데 규칙을 찾아보자.

→ 예를 들어보자.

nums = [1,1,2,3,3,4,4,8,8]

 

특징을 찾아보면 답이 되는 숫자 한 개를 제외하고는 모두 2번씩 등장하게 된다.

 

그럼 답이 되는 숫자의 좌우를 확인해서 다른 점을 확인해본다면,

→ 좌측에서는 2번째로 등장하는 수의 인덱스는 홀수임에 비해( 1의 두번째 등장하는 곳의 index가 홀수)

→ 우측에서는 2번째로 등장하는 수의 인덱스는 짝수라는 특징이 존재한다.(3,4,8의 두번째 등장하는 곳의 index가 짝수)

 

[과정]

1. Binary Search를 준비한다. left, right를 각각 0과 len(nums) - 1로 초기화 시킨다.

2. left와 right의 중간인 mid를 계산하여 mid+1과 mid-1에 있는 값을 확인한다.

3-1. 만약 양옆에 같은 값이 없다면 해당 값이 답이 되며

3-2. 만약 왼쪽에 같은 값이 있다면 현재 mid 위치가 현재의 수가 두번째로 등장하는 인덱스가 된다.

3-3. 만약 오른쪽에 같은 값이 있다면 현재 mid+1위치가 현재의 수가 두번째로 등장하는 인덱스가 된다.

4. 위에서 구한 위치의 인덱스가 홀수라면 그 수 이후에 답이 존재한다는 의미

4-2. 만약 인덱스가 짝수라면 그 수 이전에 답이 존재한다는 의미이다.

 

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        left = 0; right = len(nums) - 1;

        while(left < right):
            mid = (left + right)//2;
            last = 0;
            if nums[mid] == nums[mid - 1]:
                last = mid;
            elif nums[mid] == nums[mid + 1]:
                last = mid + 1;
            else:
                return nums[mid];
            
            if last & 1:
                left = last + 1;
            else:
                right = last - 2;
        
        return nums[left];

Time Complexity: O(logN)

시간복잡도는 이진탐색의 시간복잡도인 logN을 가지게 된다.

 

Space Complexity: O(1)

left와 right외의 다른 변수를 사용하지 않기 때문에 공간복잡도는 1이다.

 

다른 해결 방식

제약조건이 존재하여 대부분 비슷하게 풀었다.

 

 

 

문제 링크

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

Single Element in a Sorted Array - LeetCode