Python에서 O(n) 시간 및 O(1) 추가 공간에서 최대 반복 수 찾기

배열의 요소가 0에서 k-1 범위에 있는 경우 크기가 n인 배열이 있다고 가정합니다. 여기서 k는 양의 정수로 표시되고 k <=n입니다. 이 배열에서 최대 반복 수를 찾아야 합니다.

따라서 입력이 k =8 및 A =[3, 4, 4, 6, 4, 5, 2, 8]인 경우 출력은 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=A의 크기
0에서 n 사이의 i에 대해 수행
- A[A[i] 모드 k] :=A[A[i] 모드 k] + k
max_val :=A[0]
결과 :=0
범위 1에서 n까지의 i에 대해 수행
- A[i]> max_val이면
  - max_val :=A[i]
  - 결과 :=나는
반환 결과

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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