給定大小為 n 且數字為 k 的數組，找到出現次數超過 n / k 次的所有元素 · GeeksForGeeks 中文系列教程

# 給定大小為 n 且數字為 k 的數組，找到出現次數超過`n / k`次的所有元素 > 原文： [https://www.geeksforgeeks.org/given-an-array-of-of-size-n-finds-all-the-elements-that-appear-more-than-nk-times/](https://www.geeksforgeeks.org/given-an-array-of-of-size-n-finds-all-the-elements-that-appear-more-than-nk-times/) 給定大小為`n`的數組，找到數組中出現`n / k`次以上的所有元素。例如，如果輸入數組為`{3, 1, 2, 2, 1, 2, 2, 3, 3}`，`k`為 4，則輸出應為`[2, 3]`。請注意，數組的大小為 8（或`n = 8`），因此我們需要查找所有出現超過 2（或`8/4`）次的元素。有兩個元素出現兩次以上，即 2 和 3。 **簡單方法**是一個接一個地選擇所有元素。對于每個拾取的元素，通過遍歷數組來計數它的出現，如果`count`大于`n / k`，則打印該元素。該方法的時間復雜度為`O(n^2)`。更好的解決方案是**使用排序**。首先，使用`O(nLogn)`算法對所有元素進行排序。數組排序后，我們可以在數組的線性掃描中找到所有必需的元素。因此，此方法的總體時間復雜度為`O(nLogn)+O(n)`，即`O(nLogn)`。以下是一個有趣的`O(nk)`解決方案：我們可以使用`O(k-1)`多余空間來解決`O(nk)`時間中的上述問題。請注意，輸出中的元素不得超過`k-1`個（為什么？）。該算法主要包括三個步驟。 **1）**創建大小為`k-1`的臨時數組，以存儲元素及其計數（輸出元素將在這`k-1`個元素中）。以下是臨時數組元素的結構。 ``` struct eleCount { int element; int count; }; struct eleCount temp[]; ``` 此步驟需要`O(k)`時間。 **2）**遍歷輸入數組并為每個遍歷的元素更新`temp[]`（添加/刪除元素或增加/減少計數）。數組`temp[]`在每個步驟中存儲潛在`k-1`個候選對象。此步驟需要`O(nk)`時間。 **3）**迭代最終`k-1`個潛在候選對象（存儲在`temp[]`中）。或每個元素，請檢查其實際計數是否大于`n / k`。此步驟需要`O(nk)`時間。主要步驟是步驟 2，如何在每個點上保持`k-1`個潛在候選者？步驟 2 中使用的步驟類似于著名的游戲： [俄羅斯方塊](http://en.wikipedia.org/wiki/Tetris)。我們在俄羅斯方塊中將每個數字視為一個部分，這屬于我們的臨時數組`temp[]`。我們的任務是嘗試將相同的數字堆疊在同一列上（臨時數組中的計數增加）。 ``` Consider k = 4, n = 9 Given array: 3 1 2 2 2 1 4 3 3 i = 0 3 _ _ temp[] has one element, 3 with count 1 i = 1 3 1 _ temp[] has two elements, 3 and 1 with counts 1 and 1 respectively i = 2 3 1 2 temp[] has three elements, 3, 1 and 2 with counts as 1, 1 and 1 respectively. i = 3 - - 2 3 1 2 temp[] has three elements, 3, 1 and 2 with counts as 1, 1 and 2 respectively. i = 4 - - 2 - - 2 3 1 2 temp[] has three elements, 3, 1 and 2 with counts as 1, 1 and 3 respectively. i = 5 - - 2 - 1 2 3 1 2 temp[] has three elements, 3, 1 and 2 with counts as 1, 2 and 3 respectively. ``` 現在出現了一個問題，當`temp[]`滿時該怎么辦，我們看到一個新元素–我們從元素堆棧中刪除最下面一行，即，我們在`temp[]`中將每個元素的數量減少 1。我們忽略當前元素。 ``` i = 6 - - 2 - 1 2 temp[] has two elements, 1 and 2 with counts as 1 and 2 respectively. i = 7 - 2 3 1 2 temp[] has three elements, 3, 1 and 2 with counts as 1, 1 and 2 respectively. i = 8 3 - 2 3 1 2 temp[] has three elements, 3, 1 and 2 with counts as 2, 1 and 2 respectively. ``` 最后，我們在`temp[]`中最多有`k-1`個數字。 `temp`中的元素為`{3, 1, 2}`。請注意，`temp[]`中的計數現在已無用，僅在步驟 2 中才需要計數。現在我們需要檢查`temp[]`中元素的實際計數是否大于`n / k`（`9/4`）。元素 3 和 2 的計數大于`9/4`。因此，我們打印 3 和 2。請注意，該算法不會遺漏任何輸出元素。可能有兩種可能性，許多事件在一起或分布在整個數組中。如果出現的次數在一起，則計數將很高，并且不會變為 0。如果出現的次數分散，則元素將再次以`temp[]`出現。以下是上述算法的 C++ 實現。 ``` // A C++ program to print elements with count more than n/k #include<iostream> using namespace std; // A structure to store an element and its current count struct eleCount { ????int e;? // Element ????int c;? // Count }; // Prints elements with more than n/k occurrences in arr[] of // size n. If there are no such elements, then it prints nothing. void moreThanNdK(int arr[], int n, int k) { ????// k must be greater than 1 to get some output ????if (k < 2) ???????return; ????/* Step 1: Create a temporary array (contains element ???????and count) of size k-1\. Initialize count of all ???????elements as 0 */ ????struct eleCount temp[k-1]; ????for (int i=0; i<k-1; i++) ????????temp[i].c = 0; ????/* Step 2: Process all elements of input array */ ????for (int i = 0; i < n; i++) ????{ ????????int j; ????????/* If arr[i] is already present in ???????????the element count array, then increment its count */ ????????for (j=0; j<k-1; j++) ????????{ ????????????if (temp[j].e == arr[i]) ????????????{ ?????????????????temp[j].c += 1; ?????????????????break; ????????????} ????????} ????????/* If arr[i] is not present in temp[] */ ????????if (j == k-1) ????????{ ????????????int l; ????????????/* If there is position available in temp[], then place? ??????????????arr[i] in the first available position and set count as 1*/ ????????????for (l=0; l<k-1; l++) ????????????{ ????????????????if (temp[l].c == 0) ????????????????{ ????????????????????temp[l].e = arr[i]; ????????????????????temp[l].c = 1; ????????????????????break; ????????????????} ????????????} ????????????/* If all the position in the temp[] are filled, then? ???????????????decrease count of every element by 1 */ ????????????if (l == k-1) ????????????????for (l=0; l<k; l++) ????????????????????temp[l].c -= 1; ????????} ????} ????/*Step 3: Check actual counts of potential candidates in temp[]*/ ????for (int i=0; i<k-1; i++) ????{ ????????// Calculate actual count of elements? ????????int ac = 0;? // actual count ????????for (int j=0; j<n; j++) ????????????if (arr[j] == temp[i].e) ????????????????ac++; ????????// If actual count is more than n/k, then print it ????????if (ac > n/k) ???????????cout << "Number:" << temp[i].e ????????????????<< " Count:" << ac << endl; ????} } /* Driver program to test above function */ int main() { ????cout << "First Test\n"; ????int arr1[] = {4, 5, 6, 7, 8, 4, 4}; ????int size = sizeof(arr1)/sizeof(arr1[0]); ????int k = 3; ????moreThanNdK(arr1, size, k); ????cout << "\nSecond Test\n"; ????int arr2[] = {4, 2, 2, 7}; ????size = sizeof(arr2)/sizeof(arr2[0]); ????k = 3; ????moreThanNdK(arr2, size, k); ????cout << "\nThird Test\n"; ????int arr3[] = {2, 7, 2}; ????size = sizeof(arr3)/sizeof(arr3[0]); ????k = 2; ????moreThanNdK(arr3, size, k); ????cout << "\nFourth Test\n"; ????int arr4[] = {2, 3, 3, 2}; ????size = sizeof(arr4)/sizeof(arr4[0]); ????k = 3; ????moreThanNdK(arr4, size, k); ????return 0; } ``` 輸出： ``` First Test Number:4 Count:3 Second Test Number:2 Count:2 Third Test Number:2 Count:2 Fourth Test Number:2 Count:2 Number:3 Count:2 ``` 時間復雜度：`O(nk)` 輔助空間：`O(k)` 通常會問到此問題的變體，找到所有在`O(n)`時間復雜度和`O(1)`額外空間中出現`n / 3`次或`n / 4`次的元素。 **散列**也是一種有效的解決方案。有了良好的哈希函數，我們平均可以在`O(n)`時間上解決上述問題。散列所需的額外空間將大于`O(k)`。同樣，哈希不能用于解決`O(1)`額外空間的上述變化。 **練習**：可以使用比用于`k-1`個元素的輔助存儲的數組更合適的數據結構，在`O(nLogk)`時間內解決上述問題。建議使用`O(nLogk)`方法。