비트 조작 추가문제

Question 1: Single Number 2

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

입력: [2,2,3,2]

출력: 3

---

내 풀이

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums_count = collections.Counter(nums)
        for key, value in nums_count.items():
            if value == 1:
                return key
        

결과

Runtime: 143 ms, faster than 28.13% of Python3 online submissions for Single Number II. Memory Usage: 16 MB, less than 48.42% of Python3 online submissions for Single Number II.

풀이 1: XOR 풀이

class Solution:
    def singleNumber(self, nums):    
        a = 0 
        b = 0
        for i in nums:
            a = (a ^ i) & ~b
            b = (b ^ i) & ~a
        return a
       

중요 내용

1. XOR과 NOT, AND를 이용한 비트 연산 풀이이다.

---

Question 2: Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

입력: nums = [9,6,4,2,3,5,7,0,1]

출력: 8

---

내 풀이

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        max_num = max(nums)
        all_num = list(range(max_num+1))
        for num in nums:
            if num in all_num:
                all_num.remove(num)
                
        if len(all_num):
            return all_num[0]
        
        else:
            return max_num+1

결과

Runtime: 6242 ms, faster than 5.00% of Python3 online submissions for Missing Number. Memory Usage: 15.4 MB, less than 17.18% of Python3 online submissions for Missing Number.

풀이 1: XOR 풀이

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        currxor = 0
        allxor = n
        for i in range(n):
            currxor ^= nums[i]
            allxor ^= i
        return currxor ^ allxor
       

중요 내용

1. currxor은 nums에 저장된 숫자를 xor한 연산이고 allxor은 실제로 n 까지 xor 했을때의 연산이다.
2. currxor 과 allxor을 비교하여 다른 비트만 추출하여 결과로 리턴한다.