在Python中以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的大小

  • 對於i從0到n，執行：

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

  • max_val := A[0]

  • result := 0

  • 對於i從1到n，執行：

    • 如果A[i] > max_val，則：

      • max_val := A[i]

      • result := i

  • 返回result

示例

讓我們看看下面的實現來更好地理解：

線上演示

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

更新於：2020年8月20日

518 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告