Tìm số lặp lại tối đa trong thời gian O (n) và O (1) khoảng trống thừa trong Python

Giả sử chúng ta có một mảng kích thước n, nếu các phần tử trong mảng, nằm trong khoảng từ 0 đến k-1. Trong đó k được ký hiệu là số nguyên dương và k <=n. Chúng ta phải tìm số lặp lại lớn nhất trong mảng này.

Vì vậy, nếu đầu vào là k =8 và A =[3, 4, 4, 6, 4, 5, 2, 8], thì đầu ra sẽ là 4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của A

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

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

• max_val:=A [0]

• kết quả:=0

• đối với tôi trong phạm vi từ 1 đến n, hãy thực hiện

  • nếu A [i]> max_val thì

    • max_val:=A [i]

    • kết quả:=i

• trả về kết quả

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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