540. Single Element in a Sorted Array

540. Single Element in a Sorted Array

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

Single Element in a Sorted Array - LeetCode

문제)

솔루션1) - hash 사용

단 하나의 elemnt를 제외하고 모든 원소들은 두 번 등장합니다.

hash 자료구조에 처음 나오는 element를 저장하고, 두 번째 등장하게 되면 hash에 삭제합니다.

그러면 최종적으로 한 번 등장한 원소만 hash에 남게 됩니다.

 

시간 복잡도 : O(n)

공간 복잡도 : O(n)

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        # hash
        d = {}
        for n in nums:
            if n in d:
                del d[n]
            else:
                d[n] = None
        return list(d.keys())[0]

솔루션2) Counter 객체 사용

시간 복잡도 : O(n)

공간 복잡도 : O(n)

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        counter = Counter(nums)
        for n, count in counter.items():
            if count == 1:
                return n
        return None

솔루션3) 모든 원소들은 두 번 등장

단 하나의 elemnt를 제외하고 모든 원소들은 두 번 등장하는 특징을 사용합니다.

반복문을 돌면서 i, i+1 인덱스의 값을 체크하면서 동일하지 않는 경우가 발생하면 그 요소가 한 번 등장한 값이 됩니다.

 

시간 복잡도 : O(n)

공간 복잡도 : O(1)

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        for i in range(0, len(nums) - 1, 2):
            if nums[i] != nums[i+1]:
                return nums[i]
        return nums[-1]