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

pythonserver side programmingprogramming更新于 2025/9/30 13:00:17

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

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

要解决这个问题,我们将遵循以下步骤 −

  • n := A 的大小

  • 对于范围为 0 到 n 的 i,执行

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

  • max_val := A[0]

  • result := 0

  • 对于范围为 1 到 n 的 i,执行

    • 如果 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

相关文章


有用资源