프로그래밍/LeetCode
[LeetCode][Python3] 268. Missing Number
snoopybox
2018. 11. 4. 23:43
Problem :
https://leetcode.com/problems/missing-number/
My Solution :
class Solution:
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = 0
for i, n in enumerate(nums, 1):
ans ^= i^n
return ans
Comment :
예전에 비슷한 문제를 풀었었는데, xor 연산의 아래 성질을 이용하면 된다.
n ^ n = 0
n ^ 0 = n
즉 위 방법대로 nums의 모든 원소들과 1~n까지 모든 숫자를 xor 연산시키면 한번만 등장하는 숫자가 남게 된다.
물론 정렬해서 O(nlogn)으로 푸는게 가장 손쉽게 접근하는 방법이다.