在Python中以O(n)时间和O(1)额外空间查找最大重复数字

假设我们有一个大小为n的数组，如果数组中的元素范围在0到k-1之间。其中k表示正整数，且k <= n。我们必须找到这个数组中重复次数最多的数字。

因此，如果输入类似于k = 8且A = [3, 4, 4, 6, 4, 5, 2, 8]，则输出将为4。

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

• n := A的大小

• 对于i从0到n，执行：

  • A[A[i] mod k] := A[A[i] mod k] + k

• max_val := A[0]

• result := 0

• 对于i从1到n，执行：

  • 如果A[i] > max_val，则：

    • max_val := A[i]

    • result := i

• 返回result

示例

让我们看看下面的实现来更好地理解：

在线演示

def get_max_repeating(A, k):
   n = len(A)
   for i in range(n):
      A[A[i]%k] += k
   max_val = A[0]
   result = 0
   for i in range(1, n):
      if A[i] > max_val:
         max_val = A[i]
         result = i
   return result
A = [3, 4, 4, 6, 4, 5, 2, 8]
k = 8
print(get_max_repeating(A, k))

输入

[3, 4, 4, 6, 4, 5, 2, 8], 8

输出

4

Arnab Chakraborty

更新于：2020年8月20日

518 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习