使用位陣列在 Python 中查詢陣列的重複元素

假設我們有一個包含 n 個不同數字的陣列；n 最大可以是 32,000。陣列可能包含重複項，我們不知道 n 的值。現在如果我們只有 4 千位元組的記憶體，如何顯示陣列中的所有重複項？

因此，如果輸入類似於 [2, 6, 2, 11, 13, 11]，則輸出將是 [2,11]，因為 2 和 11 在給定陣列中出現多次。

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

建立一個位元組陣列型別的資料結構 bit_arr，它具有以下方法

  • 定義建構函式，它將接收 n

  • arr := 一個大小為 (n / 2^5) + 1 的陣列，填充為 0

  • 定義一個函式 get_val()。它將接收 pos

  • index := pos / 2^5

  • bitNo := pos AND 31

  • 當 (arr[index] AND (2^bitNo)) 不等於 0 時返回 true

  • 定義一個函式 set_val()。它將接收 pos

  • index := pos / 2^5

  • bitNo := pos AND 31

  • arr[index] := arr[index] OR (2^bitNo)

  • 從主方法中執行以下操作 -

  • arr := bit_arr(320000)

  • 對於 i 從 0 到 arr 的大小，執行

    • num := arr[i]

    • 如果 arr.get_val(num) 不為零，則

      • 顯示 num

    • 否則，

    • 設定 arr 的 set_val(num)

示例

讓我們看看以下實現以更好地理解 -

class bit_arr:
   def __init__(self, n):
      self.arr = [0] * ((n >> 5) + 1)
   def get_val(self, pos):
      self.index = pos >> 5
      self.bitNo = pos & 31
      return (self.arr[self.index] & (1 << self.bitNo)) != 0
   def set_val(self, pos):
      self.index = pos >> 5
      self.bitNo = pos & 31
      self.arr[self.index] |= (1 << self.bitNo)
def is_duplicate(arr):
   arr = bit_arr(320000)
   for i in range(len(arr)):
      num = arr[i]
      if arr.get_val(num):
         print(num, end = " ")
      else:
         arr.set_val(num)
arr = [2, 6, 2, 11, 13, 11]
is_duplicate(arr)

輸入

[2, 6, 2, 11, 13, 11]

輸出

2 11

更新於: 2020-08-25

144 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告