O(n) সময়ে সর্বাধিক পুনরাবৃত্তি সংখ্যা এবং Python-এ O(1) অতিরিক্ত স্থান খুঁজুন

ধরুন আমাদের n আকারের একটি অ্যারে আছে, যদি অ্যারের উপাদানগুলি 0 থেকে k-1 এর মধ্যে থাকে। যেখানে k কে একটি ধনাত্মক পূর্ণসংখ্যা হিসাবে চিহ্নিত করা হয় এবং k <=n। আমাদের এই অ্যারেতে সর্বোচ্চ পুনরাবৃত্তি সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট হয় k =8 এবং A =[3, 4, 4, 6, 4, 5, 2, 8], তাহলে আউটপুট হবে 4।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=A
এর আকার
0 থেকে n রেঞ্জের জন্য, করুন
- A[A[i] mod k] :=A[A[i] mod k] + k
max_val :=A[0]
ফলাফল :=0
1 থেকে n রেঞ্জের জন্য, করুন
- যদি A[i]> max_val, তাহলে
  - max_val :=A[i]
  - ফলাফল :=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