Số đơn II trong Python

Giả sử chúng ta có một mảng các số nguyên không rỗng, mỗi phần tử xuất hiện ba lần trừ một phần tử xuất hiện đúng một lần. Chúng ta phải tìm một phần tử duy nhất. Vì vậy, nếu mảng là [2,2,3,2] thì đầu ra sẽ là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tìm số lớn nhất bằng cách lấy giá trị tuyệt đối của các phần tử từ mảng và lưu trữ nó vào max_num

• max_bits:=số nguyên của (log max_num cơ số 2) + 2

• list1:=một danh sách trống có kích thước max_bits và có phần tử là 0

• cho mỗi số tính bằng số -

  • pos:=0

  • trong khi num không phải là 0 và pos

    • nếu không là số lẻ, thì hãy tăng list1 [pos] lên 1

    • n:=n / 2 và tăng vị trí lên 1

• cho tôi trong phạm vi từ 0 đến max_bits

  • list1 [i]:=list1 [i] mod 3

• pos:=0, res:=0

• cho tôi trong phạm vi max_bits

  • nếu list1 [i] không phải là 0, thì result:=result + 2 ^ pos

  • pos:=pos + 1

• nếu list1 [max_bits - 1] là 1, thì res:=- (2 ^ max_bits - res)

• trả lại res

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

import math
class Solution(object):
   def singleNumber(self, nums):
      max_num = max(map(abs, nums))
      max_bits = (int)(math.log(max_num,2)) + 2
      list1 = [0 for i in range(max_bits)]
      for no in nums:
         pos = 0
         while (no != 0 and pos < max_bits):
            if (no & 1 != 0):
               list1[pos] += 1
            no >>= 1
            pos += 1
      for i in range(max_bits):
         list1[i] %= 3
      pos = 0
      result = 0
      for i in range(max_bits):
         if (list1[i] != 0):
            result += (2 ** pos)
         pos += 1
      print (list1, max_bits)
      if (list1[max_bits - 1] == 1):
         result = -(2 ** max_bits - result)
      return (result)
ob = Solution()
print(ob.singleNumber([2,2,3,2]))

Đầu vào

[2,2,3,2]

Đầu ra

[1, 1, 0] 3
3