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

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

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

在线示例

让我们看看以下实现以获得更好的理解 -

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