使用位数组在 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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告