[剑指Offer] Day 22: Bit Operation

Authored by Tony Feng

Created on May 3rd, 2022

Last Modified on May 29th, 2022

Task 1 - Q56,I. 数组中数字出现的次数

Question

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是 O(1)。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        num1, num2, xo, flag = 0, 0, 0, 1

        for num in nums:
            xo ^= num
        
        while xo & flag == 0: # Find the first 1's position
            flag = flag << 1

        for num in nums:
            if num & flag == 0: # Split the nums into two groups
                num1 ^= num
            else:
                num2 ^= num

        return [num1, num2]

Explanation

Ideas
- a XO b XO b XO b … XO b = a
- a XO b XO c XO c … XO c = a XO b
- Assuming a XO b = 1010, we can find flag = 0010 to split the nums and put a, b in different groups.
- flag = 0010 means a and b’s second bits are different.

Time Complexity: O(N)
Space Complexity: O(1)

Task 2 - Q56,II. 数组中数字出现的次数 II

Question

在一个数组 nums 中除一个数字只出现1次之外，其他数字都出现了3次。请找出那个只出现一次的数字。

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        bits = [0] * 32
        for num in nums:
            for j in range(32):
                bits[j] += num & 1
                num >>= 1
        res, m = 0, 3
        for i in range(32):
            res = res << 1
            res = res | bits[31 - i] % m

        return res if bits[31] % m == 0 else ~(res ^ 0xffffffff) # Take measures for negative number

Solution 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


'''
Three cases: a) 333 444 5; b) 333 4 555; c) 3 444 555 
'''
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        if not nums: return None
        if len(nums) == 1: return nums[0]

        nums = sorted(nums)
        n = len(nums)
        for i in range(0, n, 3):
            if i == n - 1:
                return nums[i]
            elif nums[i] == nums[i+2]:
                continue
            else:
                return nums[i]

Explanation

Solution 1
- Time Complexity: O(N)
- Space Complexity: O(1)
- Steps
  - Create an array to store counts
  - Count how many 1s in each position
  - bits[i] % 3
  - bits -> binary
  - binary -> int

Solution 2
- Time Complexity: O(N)
- Space Complexity: O(N)