LeetCode: Single Number

문제설명

• 크기가 1이상인 정수형 배열이 주어졌을 때, 하나의 원소를 제외하고 나머지 원소는 2번씩 나타난다.
• 한 번만 나타나는 원소를 찾아서 반환하라.

문제풀이

• XOR 연산을 하면 중복된 값이 소거된다.
• O(n) 시간복잡도를 갖으며 O(1) 공간 복잡도를 갖도록 풀이할 수 있다.

func singleNumber(_ nums: [Int]) -> Int {
    var buf = 0
    for num in nums {
        buf = buf ^ num
    }
    return buf
}

print(singleNumber([4,5,1,5,1])) // 4
print(singleNumber([2,2,1])) // 1
print(singleNumber([1])) // 1