在 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

