查找给定数组中出现次数最多的k个数字-yiteyi-C++库

给定一系列 N 数字和正整数 K .问题是找到 K 出现次数最多的数字，即顶部 K 频率最高的数字。如果两个数字的频率相同，则应优先考虑较大的数字。数字应按频率的降序显示。假设该阵列由 K 出现次数最多的数字。

null

例如：

输入： arr[]={3,1,4,4,5,2,6,1}， k=2 输出： 4 1 说明： 频率 4. = 2 频率 1. = 2 这两个有最大的频率和频率 4. 大于 1. .

输入： arr[]={7,10,11,5,2,5,5,7,11,8,9}， k=4 输出： 5 11 7 10 说明： 频率 5. = 3 频率 11 = 2 频率 7. = 2 频率 10 = 1 这四个有最大的频率和频率 5. 在其他国家中是最大的。

在亚马逊的采访中问道

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法1：

方法： 思考的过程应该从创造一个哈希图在HashMap中存储元素频率对。HashMap用于在固定时间内执行插入和更新。然后按频率的降序对元素频率对进行排序。这将提供有关每个元素的信息以及它们在数组中出现的次数。要获得数组的k个元素，请打印已排序数组的前k个元素。
Hashmap： HashMap是自Java1.2以来Java集合的一部分。它提供了Java映射接口的基本实现。它以（键、值）对的形式存储数据。要访问某个值，必须知道其密钥。HashMap被称为HashMap，因为它使用了一种称为哈希的技术。哈希是一种将大字符串转换为代表同一字符串的小字符串的技术。较短的值有助于索引和更快的搜索。HashSet还在内部使用HashMap。它在内部使用一个链接列表来存储键值对，HashSet和后续文章已经详细解释了这一点。 更多关于HashMap的信息>>
算法：
1. 创建一个Hashmap 陛下，以存储键值对，即元素频率对。
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;                       
                         }                       
                                   
                         // function 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:"                                     ;                       
                                                 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 occurrence.                       
                         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                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     3                                     ,                                     1                                     ,                                     4                                     ,                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     6                                     ,                                     1                                     };                       
                                                 int                                     n = arr.length;                       
                                                 int                                     k =                                     2                                     ;                       
                                   
                                                 // Function call                       
                                                 print_N_mostFrequentNumber(arr, n, k);                       
                                                 }                       
                         }                       

Python3

                         # Python3 implementation to find k numbers                       
                         # with most occurrences in the given array                       
                                   
                         # function 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)                       

Javascript

                         <script>                       
                                   
                         // JavaScript implementation to find                       
                         // k elements with max occurrence.                       
                                   
                         function                                     print_N_mostFrequentNumber(arr, n, k) {                       
                                   
                                                 let mp =                                     new                                     Map();                       
                                   
                                                 // Put count of all the                       
                                                 // distinct elements in Map                       
                                                 // with element as the key &                       
                                                 // count as the value.                       
                                                 for                                     (let 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.                       
                                   
                                                 if                                     (mp.has(arr[i])) {                       
                                                 mp.set(arr[i], mp.get(arr[i]) + 1)                       
                                                 }                                     else                                     {                       
                                                 mp.set(arr[i], 1)                       
                                                 }                       
                                                 }                       
                                   
                                                 // Create a list from elements of HashMap                       
                                                 let list = [...mp];                       
                                   
                                                 // Sort the list                       
                                                 list.sort((o1, o2) => {                       
                                                 if                                     (o1[1] == o2[1])                       
                                                 return                                     o2[0] - o1[0];                       
                                                 else                       
                                                 return                                     o2[1] - o1[1];                       
                                                 })                       
                                   
                                                 document.write(k +                                     " numbers with most occurrences are:<br>"                                     );                       
                                                 for                                     (let i = 0; i < k; i++)                       
                                                 document.write(list[i][0] +                                     " "                                     );                       
                         }                       
                                   
                                   
                         // Driver Code                       
                                   
                         let arr = [3, 1, 4, 4, 5, 2, 6, 1];                       
                         let n = arr.length;                       
                         let k = 2;                       
                                   
                         // Function call                       
                         print_N_mostFrequentNumber(arr, n, k); 1                       
                                   
                         </script>                       

输出

2 numbers with most occurrences are:
4 1

复杂性分析：

时间复杂性： O（d日志d），在哪里 D 是数组中不同元素的计数。要对数组进行排序，需要O（d log d）时间。
辅助空间： O（d），在哪里 D 是数组中不同元素的计数。为了在HashMap中存储元素，需要O（d）空间复杂度。

方法2：

方法： 创建一个哈希图在HashMap中存储元素频率对。HashMap用于在固定时间内执行插入和更新。然后使用优先级队列存储元素频率对( 最大堆 )。这将给出在优先级队列的根处具有最大频率的元素。删除优先级队列K次的顶部或根，并打印元素。插入和删除优先级队列的顶部 O（对数n） 需要时间。 优先级队列： 优先级队列是一种容器适配器，专门设计为队列的第一个元素是队列中所有元素中最大的，并且元素的顺序是非递增的（因此我们可以看到队列的每个元素都有一个优先级{fixed order}）。 有关优先级队列的详细信息： C++ STL优先级队列
算法：
1. 创建一个Hashmap 陛下，以存储键值对，即元素频率对。
2. 从头到尾遍历阵列。
3. 对于数组中的每个元素，更新 hm[array[i]]++
4. 将元素频率对存储在优先级队列中并创建优先级队列，这需要O（n）个时间。
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 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;                       
                                                 }                       
                         };                       
                                   
                         // function 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]]++;                       
                                   
                                   
                                   
                                                 // 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:"                                     ;                       
                                                 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 occurrence.                       
                         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                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     3                                     ,                                     1                                     ,                                     4                                     ,                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     6                                     ,                                     1                                     };                       
                                                 int                                     n = arr.length;                       
                                                 int                                     k =                                     2                                     ;                       
                                   
                                                 // Function call                       
                                                 print_N_mostFrequentNumber(arr, n, k);                       
                                                 }                       
                         }                       
                                   
                         // This code is contributed by Shubham Kumar Shah                       

Python3

                         # Python3 implementation to find k                       
                         # numbers with most occurrences in                       
                         # the given array                       
                         import                                     heapq                       
                                   
                         # Function to print the k numbers with                       
                         # most occurrences                       
                         def                                     print_N_mostFrequentNumber(arr, n, k):                       
                                   
                                                 mp                                     =                                     dict                                     ()                       
                                   
                                                 # Put count of all the distinct elements                       
                                                 # in dictionary with element as the                       
                                                 # key & count as the value.                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
                                                 if                                     arr[i]                                     not                                     in                                     mp:                       
                                                 mp[arr[i]]                                     =                                     0                       
                                                 else                                     :                       
                                                 mp[arr[i]]                                     +                                     =                                     1                       
                                   
                                                 # Using heapq data structure                       
                                                 heap                                     =                                     [(value, key)                                     for                                     key,                       
                                                 value                                     in                                     mp.items()]                       
                                   
                                                 # Get the top k elements                       
                                                 largest                                     =                                     heapq.nlargest(k, heap)                       
                                   
                                                 # Insert the data from the map to                       
                                                 # the priority queue                       
                                                 print                                     (k,                                     " numbers with most "                       
                                                 "occurrences are:"                                     , sep                                     =                                     "")                       
                                   
                                                 # Print the top k elements                       
                                                 for                                     i                                     in                                     range                                     (k):                       
                                                 print                                     (largest[i][                                     1                                     ], end                                     =                                     " "                                     )                       
                                   
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                   
                                                 arr                                     =                                     [                                     3                                     ,                                     1                                     ,                                     4                                     ,                                     4                                     ,                                     5                                     ,                                     2                                     ,                                     6                                     ,                                     1                                     ]                       
                                                 n                                     =                                     len                                     (arr)                       
                                                 k                                     =                                     2                       
                                   
                                                 print_N_mostFrequentNumber(arr, n, k)                       
                                   
                         # This code is contributed by MuskanKalra1                       

Javascript

                         <script>                       
                         // Javascript implementation to find k                       
                         // elements with max occurrence.                       
                                   
                         function                                     print_N_mostFrequentNumber(arr,n,k)                       
                         {                       
                                                 let mp=                                     new                                     Map();                       
                                                 // Put count of all the                       
                                                 // distinct elements in Map                       
                                                 // with element as the key &                       
                                                 // count as the value.                       
                                                 for                                     (let 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.                       
                                                 if                                     (!mp.has(arr[i]))                       
                                                 mp.set(arr[i],0);                       
                                   
                                                 mp.set(arr[i],                       
                                                 mp.get(arr[i]) + 1);                       
                                                 }                       
                                   
                                                 // Create a Priority Queue                       
                                                 // to sort based on the                       
                                                 // count or on the key if the                       
                                                 // count is same                       
                                                 let queue=[...mp];                       
                                   
                                                 queue.sort(                                     function                                     (a,b){                       
                                                 if                                     (a[1]==b[1])                       
                                                 {                       
                                                 return                                     b[0]-a[0];                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 return                                     b[1]-a[1];                       
                                                 }                       
                                                 });                       
                                   
                                                 document.write(k+                                     " numbers with most "                                     +                                     "occurrences are:<br>"                                     )                       
                                                 for                                     (let i=0;i<k;i++)                       
                                                 {                       
                                                 document.write(queue[i][0]+                                     " "                                     );                       
                                                 }                       
                         }                       
                         // Driver Code                       
                         let arr=[3, 1, 4, 4, 5, 2, 6, 1 ];                       
                         let n = arr.length;                       
                         let k = 2;                       
                                   
                         // Function call                       
                         print_N_mostFrequentNumber(arr, n, k);                       
                                   
                         // This code is contributed by avanitrachhadiya2155                       
                         </script>                       

输出

2 numbers with most occurrences are:
4 1

复杂性分析：

时间复杂性： O（k log d+d），其中 D 是数组中不同元素的计数。要删除优先级最高的队列，需要O（logd）时间，因此，如果删除了k个元素，则需要O（klogd）时间，而要遍历不同的元素，则需要O（d）时间。
辅助空间： O（d），在哪里 D 是数组中不同元素的计数。为了在HashMap中存储元素，需要O（d）空间复杂度。

找到线性时间中最频繁的k 参考资料： https://www.careercup.com/question?id=5082885552865280

本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章