[파이썬 알고리즘] 19장 비트조작 - 싱글 넘버 (XOR의 사용)

https://leetcode.com/problems/single-number/

Single Number - LeetCode

 

<문제>

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

 

<예시>

Input: nums = [4,1,2,1,2] Output: 4

 

---

# x xor x = 0 이라는 것을 이용한 아이디어!
class Solution3:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

공유하고 싶은 알고리즘 풀이는 다음과 같다.

X xor X = 0 이라는 것을 이용한 풀이로, 매우 직관적이며 간단한 풀이이다.

XOR을 어떻게 활용할 수 있는지 보여주는 좋은 풀이라고 생각한다.

 

 

+) 추가 풀이

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count = defaultdict(int)
        for num in nums:
            count[num] += 1

        ans = [i for i, j in count.items() if j == 1]
        return ans[0]

class Solution2:
    def singleNumber(self, nums: List[int]) -> int:

        nums.sort()
        prev = None
        for i, num in enumerate(nums[:-1]):
            if num != prev and num != nums[i + 1]:
                return num
            prev = num
        return nums[-1]