查找給定數組中出現次數最多的 k 個數字 · GeeksForGeeks 中文系列教程

# 查找給定數組中出現次數最多的 k 個數字 > 原文： [https://www.geeksforgeeks.org/find-k-numbers-occurrences-given-array/](https://www.geeksforgeeks.org/find-k-numbers-occurrences-given-array/) 給定`n`個數字和一個正整數`k`組成的數組。問題是找到出現次數最多的`k`個數字，即找到頻率最高的前`k`個數字。如果兩個數字具有相同的頻率，則應優先選擇較大的數字。數字應按其頻率降序顯示。假設該數組由出現次數最多的`k`個數字組成。 **示例**： ``` Input: arr[] = {3, 1, 4, 4, 5, 2, 6, 1}, k = 2 Output: 4 1 Explanation: Frequency of 4 = 2 Frequency of 1 = 2 These two have the maximum frequency and 4 is larger than 1. Input : arr[] = {7, 10, 11, 5, 2, 5, 5, 7, 11, 8, 9}, k = 4 Output: 5 11 7 10 Explanation: Frequency of 5 = 3 Frequency of 11 = 2 Frequency of 7 = 2 Frequency of 10 = 10 These four have the maximum frequency and 10 is largest among rest. ``` **方法 1**： * **方法**：思維過程應從創建[`HashMap`](http://www.geeksforgeeks.org/java-util-hashmap-in-java/)開始，以將元素頻率對存儲在`HashMap`中。 `HashMap`用于在固定時間內執行插入和更新。然后以頻率降序對元素-頻率對進行排序。這給出了有關每個元素及其在數組中存在的次數的信息。要獲取數組的`k`個元素，請打印已排序數組的前`k`個元素。 * **`Hashmap`**：`HashMap`是 Java 1.2 以來的 Java 集合的一部分。它提供了 Java `Map`接口的基本實現。它以（鍵，值）對存儲數據。要訪問一個值，必須知道其鍵。 `HashMap`被稱為哈希映射，因為它使用了一種稱為哈希的技術。哈希是一種將大字符串轉換為代表相同字符串的小字符串的技術。較短的值有助于索引編制和更快的搜索。 `HashSet`還內部使用`HashMap`。它在內部使用鏈接列表來存儲已在`HashSet`中詳細解釋的鍵值對以及其他文章。 [*有關`HashMap`的更多信息*](http://www.geeksforgeeks.org/java-util-hashmap-in-java/) * **算法**： 1. 創建一個`Hashmap hm`，以存儲鍵值對，即元素頻率對。 2. 從頭到尾遍歷數組。 3. 對于數組中的每個元素更新`hm[array[i]]++` 4. 將元素頻率對存儲在向量中，然后按頻率降序對向量進行排序。 5. 打印排序數組的前`k`個元素。 * **實現**： ## C++ ``` // C++ implementation to find k numbers with most // occurrences in the given array #include <bits/stdc++.h> using namespace std; // comparison function to sort the 'freq_arr[]' bool compare(pair<int, int> p1, pair<int, int> p2) { ????// if frequencies of two elements are same ????// then the larger number should come first ????if (p1.second == p2.second) ????????return p1.first > p2.first; ????// sort on the basis of decreasing order ????// of frequencies ????return p1.second > p2.second; } // funnction to print the k numbers with most occurrences void print_N_mostFrequentNumber(int arr[], int n, int k) { ????// unordered_map 'um' implemented as frequency hash table ????unordered_map<int, int> um; ????for (int i = 0; i < n; i++) ????????um[arr[i]]++; ????// store the elements of 'um' in the vector 'freq_arr' ????vector<pair<int, int> > freq_arr(um.begin(), um.end()); ????// sort the vector 'freq_arr' on the basis of the ????// 'compare' function ????sort(freq_arr.begin(), freq_arr.end(), compare); ????// display the top k numbers ????cout << k << " numbers with most occurrences are:\n"; ????for (int i = 0; i < k; i++) ????????cout << freq_arr[i].first << " "; } // Driver program to test above int main() { ????int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????int k = 2; ????print_N_mostFrequentNumber(arr, n, k); ????return 0; } ``` ## Java ``` // Java implementation to find k elements with max occurence. import java.util.*; public class KFrequentNumbers { ????static void print_N_mostFrequentNumber(int[] arr, int n, int k) ????{ ????????Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); ????????// Put count of all the distinct elements in Map ????????// with element as the key & count as the value. ????????for (int i = 0; i < n; i++) { ????????????// Get the count for the element if already? ????????????// present in the Map or get the default value ????????????// which is 0\. ????????????mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1); ????????} ????????// Create a list from elements of HashMap ????????List<Map.Entry<Integer, Integer> > list =? ??????????new ArrayList<Map.Entry<Integer, Integer> >(mp.entrySet()); ????????// Sort the list ????????Collections.sort(list, new Comparator<Map.Entry<Integer, Integer> >() { ????????????public int compare(Map.Entry<Integer, Integer> o1, ???????????????????????????????Map.Entry<Integer, Integer> o2) ????????????{ ????????????????if (o1.getValue() == o2.getValue()) ????????????????????return o2.getKey() - o1.getKey(); ????????????????else ????????????????????return o2.getValue() - o1.getValue(); ????????????} ????????}); ????????for (int i=0; i<k; i++) ???????????System.out.println(list.get(i).getKey()); ????} ????// Driver Code to test the code. ????public static void main(String[] args) ????{ ????????int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 }; ????????int n = arr.length; ????????int k = 2; ????????print_N_mostFrequentNumber(arr, n, k); ????} } ``` ## Python3 ``` # Python3 implementation to find k numbers? # with most occurrences in the given array? # funnction to print the k numbers with # most occurrences? def pr_N_mostFrequentNumber(arr, n, k): ????um = {} ????for i in range(n): ????????if arr[i] in um: ????????????um[arr[i]] += 1 ????????else: ????????????um[arr[i]] = 1 ????a = [0] * (len(um)) ????j = 0 ????for i in um: ????????a[j] = [i, um[i]] ????????j += 1 ????a = sorted(a, key = lambda x : x[0], ?????????????????????????reverse = True) ????a = sorted(a, key = lambda x : x[1],? ?????????????????????????reverse = True) ????# display the top k numbers? ????print(k, "numbers with most occurrences are:") ????for i in range(k): ????????print(a[i][0], end = " ") # Driver code? if __name__ =="__main__": ????arr = [3, 1, 4, 4, 5, 2, 6, 1] ????n = 8 ????k = 2 ????pr_N_mostFrequentNumber(arr, n, k) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10) ``` [ **輸出**： ``` 2 numbers with most occurrences are: 4 1 ``` * **復雜度分析**： * **時間復雜度**： `O(d log d)`，其中`d`是數組中不同元素的計數。要對數組排序需要`O(d log d)`時間。 * **輔助空間**： `O(d)`，其中`d`是數組中不同元素的計數。要將元素存儲在`HashMap`中，需要`O(d)`空間復雜性。 **方法 2**： * **Approach:** Create a [HashMap](http://www.geeksforgeeks.org/java-util-hashmap-in-java/) to store element-frequency pair in the HashMap. HashMap is used to perform insertion and updation in constant time. Then use a priority queue to store the element-frequency pair ([Max-Heap](https://www.geeksforgeeks.org/max-heap-in-java/)). This gives the element which has maximum frequency at the root of the Priority Queue. Remove the top or root of Priority Queue K times and print the element. To insert and delete the top of the priority queue *O(log n)* time is required. **優先級隊列**：優先級隊列是一種容器適配器，經過專門設計，使得隊列中的第一個元素是隊列中所有元素中最大的，并且元素的順序是非遞增的（因此我們可以看到隊列中的每個元素都具有優先級{固定順序}）。 *有關優先級隊列的更多信息*：[C++ STL `priority_queue`](https://www.geeksforgeeks.org/priority-queue-container-adaptors-the-c-standard-template-library-stl/) * **算法**： 1. 創建一個`Hashmap hm`，以存儲鍵值對，即元素頻率對。 2. 從頭到尾遍歷數組。 3. 對于數組中的每個元素更新`hm[array[i]]++` 4. 將元素頻率對存儲在優先級隊列中并創建優先級隊列，這需要`O(n)`時間。 5. 運行`k`次循環，并在每次迭代中刪除優先級隊列的頂部并打印該元素。 * **實現**： ## CPP ``` // C++ implementation to find k numbers with most // occurrences in the given array #include <bits/stdc++.h> using namespace std; // comparison function defined for the priority queue struct compare { ????bool operator()(pair<int, int> p1, pair<int, int> p2) ????{ ????????// if frequencies of two elements are same ????????// then the larger number should come first ????????if (p1.second == p2.second) ????????????return p1.first < p2.first; ????????// insert elements in the priority queue on the basis of ????????// decreasing order of frequencies ????????return p1.second < p2.second; ????} }; // funnction to print the k numbers with most occurrences void print_N_mostFrequentNumber(int arr[], int n, int k) { ????// unordered_map 'um' implemented as frequency hash table ????unordered_map<int, int> um; ????for (int i = 0; i < n; i++) ????????um[arr[i]]++; ????// store the elements of 'um' in the vector 'freq_arr' ????vector<pair<int, int> > freq_arr(um.begin(), um.end()); ????// priority queue 'pq' implemented as max heap on the basis ????// of the comparison operator 'compare' ????// element with the highest frequency is the root of 'pq' ????// in case of conflicts, larger element is the root ????priority_queue<pair<int, int>, vector<pair<int, int> >, ???????????????????compare> ????????pq(um.begin(), um.end()); ????// display the top k numbers ????cout << k << " numbers with most occurrences are:\n"; ????for (int i = 1; i <= k; i++) { ????????cout << pq.top().first << " "; ????????pq.pop(); ????} } // Driver program to test above int main() { ????int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????int k = 2; ????print_N_mostFrequentNumber(arr, n, k); ????return 0; } ``` ## Java ``` // Java implementation to find k elements with max occurence. import java.util.*; public class KFrequentNumbers { ????static void print_N_mostFrequentNumber(int[] arr, int n, int k) ????{ ????????Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); ????????// Put count of all the distinct elements in Map ????????// with element as the key & count as the value. ????????for (int i = 0; i < n; i++) { ????????????// Get the count for the element if already present in the Map ????????????// or get the default value which is 0\. ????????????mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1); ????????} ????????// Create a Priority Queue to sort based on the count ????????// or on the key if the count is same ????????PriorityQueue<Map.Entry<Integer, Integer> > queue =? ???????????new PriorityQueue<>( ????????????(a, b) -> a.getValue().equals(b.getValue()) ?? ??????????????????????Integer.compare(b.getKey(), a.getKey()) :? ??????????????????????Integer.compare(b.getValue(), a.getValue())); ????????// Insert the data from the map to the Priority Queue. ????????for (Map.Entry<Integer, Integer> entry : mp.entrySet()) ????????????queue.offer(entry); ????????// Print the top k elements ????????for (int i = 0; i < k; i++) { ????????????System.out.println(queue.poll().getKey()); ????????} ????} ????// Driver Code to test the code. ????public static void main(String[] args) ????{ ????????int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 }; ????????int n = arr.length; ????????int k = 2; ????????print_N_mostFrequentNumber(arr, n, k); ????} } // This code is contributed by Shubham Kumar Shah ``` **輸出**： ``` 2 numbers with most occurrences are: 4 1 ``` * **復雜度分析**： * **時間復雜度**： `O(k log d + d)`，其中`d`是數組中不同元素的計數。要刪除優先隊列的頂部，需要`O(log d)`時間，因此，如果刪除了`k`個元素，則需要`O(k log d)`時間，并且需要遍歷不同元素`O(d)`時間。 * **輔助空間**：`O(d)`，其中`d`是數組中不同元素的計數。要將元素存儲在`HashMap`中，需要`O(d)`空間復雜性。 [**查找線性時間中最常見的`k`個**](https://www.geeksforgeeks.org/find-k-most-frequent-in-linear-time/) **參考**： [https://www.careercup.com/question?id=5082885552865280](https://www.careercup.com/question?id=5082885552865280)