Tìm số lặp lại nhiều nhất trong O(n) thời gian và O(1) bộ nhớ thêm trong Python

Cho mảng kích thước n, các phần tử trong khoảng [0, k-1] với k ≤ n. Tìm số xuất hiện nhiều nhất.

Ví dụ: k=8, A=[3,4,4,6,4,5,2,8] → kết quả 4.

Giải thuật (Kỹ thuật đánh dấu chỉ số)

Sử dụng chính mảng để lưu tần suất: với mỗi phần tử A[i], tăng giá trị tại chỉ số A[i] % k thêm k. Sau đó phần tử có giá trị lớn nhất chính là số lặp nhiều nhất.

• Duyệt i từ 0 đến n-1: A[A[i] % k] += k
• Tìm chỉ số i có A[i] lớn nhất → đó là kết quả.

Lưu ý: phương pháp này sửa đổi mảng gốc.

Ví dụ

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))

Đầu vào

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

Đầu ra

4