在Python中使用位数组查找数组的重复项
假设我们有n个不同数字组成的数组；n最多为32,000。该数组可能有重复的条目，我们不知道n的值是什么。现在，如果我们只有4KB的内存，将如何显示数组中的所有重复项？
因此，如果输入类似于[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