540. Single Element in a Sorted Array

540. Single Element in a Sorted Array

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

---

어떤 List에 int 값이 들어있는데 하나의 숫자만 한개가 있고, 나머지는 모두 두개씩 있을 때, 그 하나만 존재하는 숫자를 리턴하는 것입니다. for문 두번 돌리면 간단히 해결하지만 조건이 붙었습니다.

공간 복잡도 O(1)에, 시간 복잡도가 (logN)입니다.

logN이기 때문에 분할해야 하는데, 저는 재귀로 나누어가면서 풀었습니다.

List의 정 가운데를 자른다고 생각하면 현재 숫자를 기준으로 왼쪽이 홀수개의 리스트면 왼쪽에 찾고자 하는 숫자가 있을 것이고 오른쪽이 홀수개의 리스트면 오른쪽에 있을 것입니다. 왜냐하면 모든 숫자는 두 개씩 있을테니까요.

현재 숫자와 왼쪽이 같으면 그 숫자를 제외한 나머지를 보고, 마찬가지로 오른쪽과 같다면 현재와 오른쪽 같은 숫자를 제외한 나머지 리스트의 길이를 보는 것입니다.

class Solution(object):
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return self.solve(nums, 0, len(nums)-1)
    
    def solve(self, nums, start, end):
        if start >= end:
            return nums[start]
        
        mid = (start+end)/2
        left = (start+end)/2-1
        right = (start+end)/2+1
        
        if nums[mid] == nums[left]:
            if len(nums[:left]) % 2 != 0:
                return self.solve(nums, 0, left-1)
            else:
                return self.solve(nums, right, end)
        else:
            if len(nums[:mid]) % 2 != 0:
                return self.solve(nums, 0, left)
            else:
                return self.solve(nums, right+1, end)