पायथन में O(n) समय और 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 की सीमा में, करें

  • ए [ए [i] मॉड के]:=ए [ए [i] मॉड के] + के

• max_val :=A[0]

• परिणाम:=0

• 1 से n की सीमा में i के लिए, करें

  • अगर A[i]> max_val, तो

    • max_val:=ए[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

आउटपुट

4