# 在`O(n)`時間和`O(1)`多余空間中找到最大重復數 > 原文： [https://www.geeksforgeeks.org/find-the-maximum-repeating-number-in-ok-time/](https://www.geeksforgeeks.org/find-the-maximum-repeating-number-in-ok-time/) 給定大小為`n`的數組，該數組包含從 0 到`k-1`范圍內的數字，其中`k`是正整數，`k <= n`。在此數組中找到最大重復數。 例如，假設`k`為 10，則給定數組為`arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}`，最大重復數將為 2。期望的時間復雜度為`O(n)`，允許的額外空間為`O(1)`。 允許對數組進行修改。 **樸素的方法**是運行兩個循環，外循環一個接一個地拾取一個元素，內循環計算被拾取元素的出現次數。 最后返回具有最大計數的元素。 該方法的時間復雜度為`O(n ^ 2)`*。 **更好的方法**是創建一個大小為`k`的計數數組，并將`count[]`的所有元素初始化為 0。對輸入數組的所有元素以及每個元素`arr[i]`進行迭代，增加`count[arr[i]]`。 最后，迭代`count[]`并返回具有最大值的索引。 這種方法花費`O(n)`時間，但需要`O(k)`空間。 以下是`O(n)`時間和`O(1)`額外空間方法。 讓我們用一個簡單的例子來理解該方法，其中`arr[] = {2, 3, 3, 5, 3, 4, 1, 1, 7}`，`k = 8`，`n = 8`（`arr[]`中的元素數）。 **1）**迭代輸入數組`arr[]`，對于每個元素`arr[i]`，將`arr[arr[i] % k]`遞增`k`（`arr []`變成`{2, 11, 11, 29, 11, 12, 1, 15}`） **2）**在修改后的數組中找到最大值（最大值為 29）。 最大值的索引是最大重復元素（索引 29 是 3）。 **3）**如果我們想找回原始數組，可以再遍歷該數組一次，并執行`arr[i] = arr [i] % k`其中`i`從 0 到`n-1`變化。 *以上算法如何工作？* 由于我們使用`arr[i] % k`作為索引，并在索引`arr[i] % k`處添加值`k`，因此該索引為 等于最大重復元素最后將具有最大值。 注意，`k`在等于最大重復元素的索引處被添加最大次數，并且所有數組元素都小于`k`。 以下是上述算法的 C++ 實現。 ## C++ ```cpp // C++ program to find the maximum repeating number #include<iostream> using namespace std; // Returns maximum repeating element in arr[0..n-1]. // The array elements are in range from 0 to k-1 int maxRepeating(int* arr, int n, int k) { ????// Iterate though input array, for every element ????// arr[i], increment arr[arr[i]%k] by k ????for (int i = 0; i< n; i++) ????????arr[arr[i]%k] += k; ????// Find index of the maximum repeating element ????int max = arr[0], result = 0; ????for (int i = 1; i < n; i++) ????{ ????????if (arr[i] > max) ????????{ ????????????max = arr[i]; ????????????result = i; ????????} ????} ????/* Uncomment this code to get the original array back ???????for (int i = 0; i< n; i++) ??????????arr[i] = arr[i]%k; */ ????// Return index of the maximum element ????return result; } // Driver program to test above function int main() { ????int arr[] = {2, 3, 3, 5, 3, 4, 1, 7}; ????int n = sizeof(arr)/sizeof(arr[0]); ????int k = 8; ????cout << "The maximum repeating number is " << ?????????maxRepeating(arr, n, k) << endl; ????return 0; } ```