在Python中使用位数组查找数组的重复项

假设我们有n个不同数字组成的数组；n最多为32,000。该数组可能有重复的条目，我们不知道n的值是什么。现在，如果我们只有4 KB的内存，将如何显示数组中的所有重复项？

因此，如果输入类似于[2，6，2，11，11，13，11]，则输出将为[2,11]，因为2和11在给定数组中出现多次。

为了解决这个问题，我们将遵循以下步骤-

创建一个字节数组类型的数据结构bit_arr，它具有以下方法

• 定义构造函数这将花费n

• arr：=大小为（n / 2 ^ 5）+ 1的数组，用0填充

• 定义一个函数get_val()。这将需要pos

• 索引：= pos / 2 ^ 5

• bitNo：=位置与31

• 当（arr [index] AND（2 ^ bitNo））不等于0时返回true

• 定义一个函数set_val()。这将需要pos

• 索引：= pos / 2 ^ 5

• bitNo：=位置与31

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

• 从主要方法中，执行以下操作-

• arr：= bit_arr(320000)

• 对于范围在0到arr大小之间的i，执行

• 显示数字

• num：= arr [i]

• 如果arr.get_val(num)不为零，则

• 除此以外，

• set_val(num)的arr

示例

让我们看下面的实现以更好地理解-

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