136. Single Number

문제 링크 : https://leetcode.com/problems/kth-largest-element-in-an-array/

주어진 nums에서 단 하나의 숫자를 찾는 문제이다.

처음에는 간단하게 count함수를 이용하여 찾는 방법을 이용해보았다.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        for i in nums:
            if nums.count(i) == 1:
                return i

그렇지만
Runtime: 9055 ms, faster than 5.00% of Python3 online submissions for Single Number.
Memory Usage: 16.8 MB, less than 50.51% of Python3 online submissions for Single Number.

런타임도 오래 걸리고
count의 시간복잡도는 O(n)이기 떄문에
You must implement a solution with a linear runtime complexity and use only constant extra space.
문제에서 원하는 해법이 아니다.
(같은 이유로 hashmap을 이용하는 것도 부합하지 않음)

다른 방법으로는 비트 연산자 xor를 이용하여 푸는 방법이 있다.

^

0 ^ 0 = 0

0 ^ X = X

X ^ 0 = X

X ^ X = 0

위의 연산 결과들을 참고하여 풀어본다면
ex. nums = [4,1,2,1,2]

1^1 2^2는 0이므로
최종적으로 0^4 = 4이므로
4를 반환하면 된다

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in nums:
            res^=i
        return res

Runtime: 208 ms, faster than 47.43% of Python3 online submissions for Single Number.
Memory Usage: 16.6 MB, less than 84.63% of Python3 online submissions for Single Number.