使用 Python 中的位数组查找数组的重复项
pythonserver side programmingprogramming更新于 2025/10/10 5:32:17
假设我们有一个包含 n 个不同数字的数组;n 最多可以为 32,000。数组可能有重复的条目,我们不知道 n 的值是多少。现在,如果我们只有 4 KB 的内存,如何显示数组中的所有重复项?
因此,如果输入为 [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)
对于 0 到 arr 大小范围内的 i,执行
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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

