Pythonでビット配列を使用して配列の重複を検索する

n個の異なる数値の配列があるとします。 nは最大で32,000にすることができます。配列に重複するエントリがある可能性があり、nの値がわかりません。 4キロバイトのメモリしかない場合、アレイ内のすべての重複をどのように表示しますか？

したがって、入力が[2、6、2、11、13、11]の場合、2と11が指定された配列に複数回表示されるため、出力は[2,11]になります。

これを解決するには、次の手順に従います-

1バイト配列型のデータ構造bit_arrを作成します。次のメソッドがあります

• コンストラクターの定義これにはnが必要です

• arr：=サイズの配列（n / 2 ^ 5）+ 1、0で埋める

• 関数get_val（）を定義します。これには時間がかかります

• インデックス：=pos / 2 ^ 5

• bitNo：=pos AND 31

• （arr [index] AND（2 ^ bitNo））が0と同じでない場合はtrueを返します

• 関数set_val（）を定義します。これには時間がかかります

• インデックス：=pos / 2 ^ 5

• bitNo：=pos AND 31

• arr [index]：=arr [index] OR（2 ^ bitNo）

• メインの方法から、次のようにします-

• arr：=bit_arr（320000）

• 0からarrのサイズまでの範囲のiの場合、実行します

  • num：=arr [i]

  • arr.get_val（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