Python程式：查詢陣列中元素的最大異或值

假設我們有一個名為 nums 的陣列，其中包含非負值。我們還有另一個名為 queries 的陣列，其中 queries[i] 包含一個對 (xi, mi)。第 i 個查詢的答案是 xi 與 nums 中任何小於或等於 mi 的元素進行按位異或運算的最大值。如果 nums 中的所有元素都大於 mi，則答案為 -1。因此，我們必須找到一個答案陣列，其大小與查詢的大小相同，並且 answer[i] 是第 i 個查詢的答案。

因此，如果輸入類似於 nums = [0,1,2,3,4] queries = [[3,1],[1,3],[5,6]]，則輸出將為 [3,3,7]，因為

  • 0 和 1 不大於 1。0 XOR 3 = 3 且 1 XOR 3 = 2，這裡這兩個數中較大的一個是 3。

  • 1 XOR 2 = 3。

  • 5 XOR 2 = 7。

為了解決這個問題，我們將遵循以下步驟 -

  • m := nums 的大小

  • n := queries 的大小

  • queries = 為每個索引 i 和查詢中的對 (x, limit) 建立一個三元組 (i, x, limit)

  • 根據 limit 對 queries 進行排序

  • nums := 對列表 nums 進行排序

  • res := 一個大小為 n 的陣列，並用 0 填充

  • 對於 k 從 31 到 0，遞減 1，執行

    • prefixes := 一個新的集合

    • j := 0

    • 對於查詢中的每個索引 i 和值 (x, limit)，執行

      • 當 j <= m - 1 且 nums[j] <= limit 時，執行

        • 將 nums[j] 右移 k 位並插入到 prefixes 中

        • j := j + 1

      • 如果 prefixes 為空，則

        • res[i] := -1

      • 否則，

        • res[i] = res[i]/2 的商

        • target := res[i] XOR 1

        • 如果 (x 右移 k 位後) XOR target 在 prefixes 中，則

          • res[i] := target

  • 返回 res

示例

讓我們看看以下實現以獲得更好的理解

def solve(nums, queries):
   m, n = len(nums), len(queries)
   queries = sorted(((i, x, limit) for i, (x, limit) in
enumerate(queries)), key=lambda x: x[2])
   nums = sorted(nums)
   res = [0] * n
   for k in range(31, -1, -1):
      prefixes = set()
      j = 0
      for i, x, limit in queries:
         while j <= m - 1 and nums[j] <= limit:
            prefixes.add(nums[j] >> k)
            j += 1
         if not prefixes:
            res[i] = -1
         else:
            res[i] <<= 1
            target = res[i] ^ 1
            if (x >> k) ^ target in prefixes:
               res[i] = target
   return res

nums = [0,1,2,3,4]
queries = [[3,1],[1,3],[5,6]]
print(solve(nums, queries))

輸入

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

輸出

[3, 3, 7]

更新於: 2021年10月7日

247 次檢視

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告