Single Number II ใน Python

สมมติว่าเรามีอาร์เรย์จำนวนเต็มที่ไม่ว่างเปล่า ทุกองค์ประกอบปรากฏขึ้นสามครั้งยกเว้นหนึ่งรายการซึ่งปรากฏเพียงครั้งเดียว เราต้องหาองค์ประกอบเดียว ดังนั้นหากอาร์เรย์เป็น [2,2,3,2] ผลลัพธ์จะเป็น 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• หาจำนวนสูงสุดโดยนำค่าสัมบูรณ์ขององค์ประกอบจากอาร์เรย์มาเก็บไว้ใน max_num

• max_bits :=จำนวนเต็มของ (บันทึก max_num ฐาน 2) + 2

• list1 :=รายการขนาด max_bits ว่างและมีองค์ประกอบเป็น 0

• สำหรับแต่ละ num เป็น num -

  • ตำแหน่ง :=0

  • ในขณะที่ num ไม่ใช่ 0 และ pos

    • ถ้าไม่เป็นเลขคี่ ให้เพิ่ม list1[pos] ขึ้น 1

    • n :=n / 2 และเพิ่ม pos 1

• สำหรับฉันอยู่ในช่วง 0 ถึง max_bits

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

• ตำแหน่ง :=0, ความละเอียด :=0

• สำหรับฉันอยู่ในช่วง max_bits

  • ถ้า list1[i] ไม่ใช่ 0 แล้ว result :=result + 2^pos

  • pos :=pos + 1

• ถ้า list1[max_bits - 1] เป็น 1 แล้ว res :=-(2^max_bits - res)

• ผลตอบแทน

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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]))

อินพุต

[2,2,3,2]

ผลลัพธ์

[1, 1, 0] 3
3