โปรแกรมค้นหารายการองค์ประกอบที่น้อยกว่าขีด จำกัด และ XOR สูงสุดใน Python

สมมติว่าเรามีรายการตัวเลขและรายการข้อความค้นหาที่แต่ละข้อความค้นหามี [x, จำกัด] เราต้องหารายชื่อที่สำหรับแต่ละข้อความค้นหา [x, limit] เราพบองค์ประกอบ e เป็น nums ซึ่ง e ≤ limit และ e XOR x ถูกขยายให้ใหญ่สุด หากไม่มีองค์ประกอบดังกล่าว ให้คืนค่า -1

ดังนั้น หากอินพุตเป็น nums =[3, 5, 9] คำสั่ง =[[4, 6],[2, 0]] ผลลัพธ์จะเป็น [3, -1] สำหรับข้อความค้นหาแรก เราสามารถใช้ 2 หรือ 4 ในจำนวน 3 ^ 4 =7 ในขณะที่ 5 ^ 4 =3 ดังนั้นเราจึงเลือก 3 ซึ่งให้ XOR ที่ใหญ่กว่า ในแบบสอบถามที่สอง ไม่มีตัวเลขดังกล่าวที่น้อยกว่าหรือเท่ากับ 0 ดังนั้นเราจึงตั้งค่าเป็น -1

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

• พยายาม :=แผนที่ใหม่

• กำหนดฟังก์ชัน bits() นี่จะใช้เวลาฉัน

• ส่งคืนการแสดงไบนารี 32 บิตของ i

• กำหนดฟังก์ชันแทรก นี่จะใช้เวลาฉัน

• โหนด :=พยายาม

• สำหรับแต่ละ c เป็นบิต (i) ทำ

  • node :=ถ้า c ไม่อยู่ใน node ให้แทรก map เปล่าเข้าไป

• โหนด[2] :=ผม

• กำหนดฟังก์ชั่น query() นี่จะใช้เวลาฉัน

• โหนด :=พยายาม

• สำหรับแต่ละ c เป็นบิต (i) ทำ

  • rc :=c XOR 1

  • โหนด :=โหนด[rc] ถ้ามีอยู่มิฉะนั้น node[c]

• โหนดกลับ[2]

• จากวิธีหลักให้ทำดังต่อไปนี้ -

• เรียงลำดับรายการ A

• B :=รายการองค์ประกอบในรูปแบบ (i, x, ขีด จำกัด ) สำหรับดัชนีการค้นหาแต่ละรายการ i และค่าการสืบค้น x และขีดจำกัด แล้วจัดเรียงตามขีดจำกัด

• (j, n, ans) :=(0, size of A , รายการขนาดเดียวกับการสืบค้น, เติมด้วย -1)

• สำหรับแต่ละดัชนี i และค่า x และขีดจำกัดใน B ให้ทำ

  • ในขณะที่ j

    • แทรก(A[j])

    • เจ :=เจ + 1

  • ถ้า j ไม่ใช่ศูนย์ แล้ว

    • ตอบ[i] :=แบบสอบถาม(x)

• กลับมาอีกครั้ง

ตัวอย่าง (Python)

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

class Solution:
   def solve(self, A, queries):
      trie = {}
      def bits(i):
         return map(int, bin(i)[2:].zfill(32))
      def insert(i):
         node = trie
         for c in bits(i):
            node = node.setdefault(c, {})
         node[2] = i
      def query(i):
         node = trie
         for c in bits(i):
            rc = c ^ 1
            node = node.get(rc, node.get(c))
         return node[2]
      A.sort()
      B = sorted([(i, x, limit) for i, (x, limit) in enumerate(queries)], key=lambda x: x[2])
j, n, ans = 0, len(A), [-1] * len(queries)
      for i, x, limit in B:
         while j < n and A[j] <= limit:
            insert(A[j])
            j += 1
         if j:
            ans[i] = query(x)
      return ans
ob = Solution()
nums = [3, 5, 9]
queries = [
   [4, 6],
   [2, 0]
]
print(ob.solve(nums, queries))

อินพุต

[3, 5, 9], [[4, 6],[2, 0]]

ผลลัพธ์

[3, -1]