Given an array of N numbers and a positive integer K. The problem is to find K numbers with the most occurrences, i.e., the top K numbers having the maximum frequency. If two numbers have the same frequency then the number with a larger value should be given preference. The numbers should be displayed in decreasing order of their frequencies. It is assumed that the array consists of at least K numbers.
Examples:
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 = 1
These four have the maximum frequency and 5 is largest among rest.
Find K most occurring elements in the given Array using Map
To solve the problem using this approach follow the below idea:
create a Map to store the element-frequency pair. Map is used to perform insertion and updation in constant time. Then sort the element-frequency pair in decreasing order of frequency. This gives the information about each element and the number of times they are present in the array. To get K elements of the array, print the first K elements of the sorted array.
Follow the given steps to solve the problem:
- Create a map mp, to store key-value pair, i.e. element-frequency pair.
- Traverse the array from start to end.
- For every element in the array update mp[array[i]]++
- Store the element-frequency pair in a vector and sort the vector in decreasing order of frequency.
- Print the first k elements of the sorted array.
Below is the Implementation of the above approach:
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 occurrencesvoid print_N_mostFrequentNumber(int arr[], int N, int K){ // unordered_map 'mp' implemented as frequency hash // table unordered_map<int, int> mp; for (int i = 0; i < N; i++) mp[arr[i]]++; // store the elements of 'mp' in the vector 'freq_arr' vector<pair<int, int> > freq_arr(mp.begin(), mp.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's codeint main(){ int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 2; // Function call 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.print(list.get(i).getKey() + " "); } // Driver's 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 System.out.println( K + " numbers with most occurrences are:"); 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 occurrencesdef pr_N_mostFrequentNumber(arr, N, K): mp = {} for i in range(N): if arr[i] in mp: mp[arr[i]] += 1 else: mp[arr[i]] = 1 a = [0] * (len(mp)) j = 0 for i in mp: a[j] = [i, mp[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 codeif __name__ == "__main__": arr = [3, 1, 4, 4, 5, 2, 6, 1] N = 8 K = 2 # Function call pr_N_mostFrequentNumber(arr, N, K)# This code is contributed by# Shubham Singh(SHUBHAMSINGH10) |
C#
// C# implementation to find// k elements with max occurrence.using System;using System.Collections.Generic;public class Comparer : IComparer<KeyValuePair<int, int> > { public int Compare(KeyValuePair<int, int> p2, KeyValuePair<int, int> p1) { // If frequencies of two elements are same // then the larger number should come first if (p1.Value == p2.Value) return p1.Key.CompareTo(p2.Key); // Sort on the basis of decreasing order // of frequencies return p1.Value.CompareTo(p2.Value); }}public class KFrequentNumbers { static void print_N_mostFrequentNumber(int[] arr, int N, int K) { IDictionary<int, int> mp = new Dictionary<int, int>(); // 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 if (mp.ContainsKey(arr[i])) mp[arr[i]] += 1; else mp[arr[i]] = 1; } // Create a list from elements of HashMap List<KeyValuePair<int, int> > list = new List<KeyValuePair<int, int> >(); foreach(KeyValuePair<int, int> entry in mp) { list.Add(entry); } // Sort the list Comparer compare = new Comparer(); list.Sort(compare); for (int i = 0; i < K; i++) Console.Write(list[i].Key + " "); } // Driver's code public static void Main(string[] args) { int[] arr = { 3, 1, 4, 4, 5, 2, 6, 1 }; int N = arr.Length; int K = 2; Console.Write( K + " elements with most occurrences are:\n"); // Function call print_N_mostFrequentNumber(arr, N, K); }}// this code is contributed by phasing17 |
Javascript
// 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: "); for (let i = 0; i < K; i++) document.write(list[i][0] + " ");}// Driver's Codelet arr = [3, 1, 4, 4, 5, 2, 6, 1];let N = arr.length;let K = 2;// Function callprint_N_mostFrequentNumber(arr, N, K); |
Output
2 numbers with most occurrences are: 4 1
Time Complexity: O(D log D), where D is the count of distinct elements in the array
Auxiliary Space: O(D), where D is the count of distinct elements in the array
Find K most occurring elements in the given Array using Max-Heap
To solve the problem using this approach follow the below idea:
Approach: Create a Map to store element-frequency pair. Map is used to perform insertion and updation in constant time. Then use a priority queue to store the element-frequency pair (Max-Heap). The element which has maximum frequency, comes at the root of the Priority Queue. Remove the top or root of Priority Queue K times and print the element.
Follow the given steps to solve the problem:
- Create a map mp, to store key-value pair, i.e. element-frequency pair.
- Traverse the array from start to end.
- For every element in the array update mp[array[i]]++
- Store the element-frequency pair in a Priority Queue
- Run a loop k times, and in each iteration remove the root of the priority queue and print the element.
Below is the Implementation of the above approach:
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 queuestruct 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 occurrencesvoid print_N_mostFrequentNumber(int arr[], int N, int K){ // unordered_map 'mp' implemented as frequency hash // table unordered_map<int, int> mp; for (int i = 0; i < N; i++) mp[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(mp.begin(), mp.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's codeint main(){ int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 2; // Function call 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.print(queue.poll().getKey() + " "); } } // Driver's Code public static void main(String[] args) { int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 }; int N = arr.length; int K = 2; System.out.println( K + " numbers with most occurrences are:"); // 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 arrayimport heapq# Function to print the k numbers with# most occurrencesdef 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's codeif __name__ == "__main__": arr = [3, 1, 4, 4, 5, 2, 6, 1] N = len(arr) K = 2 # Function call print_N_mostFrequentNumber(arr, N, K)# This code is contributed by MuskanKalra1 |
C#
// C# implementation to find k// elements with max occurrence.using System;using System.Collections.Generic;using System.Linq;public class KFrequentNumbers { static void print_N_mostFrequentNumber(int[] arr, int N, int K) { Dictionary<int, int> mp = new Dictionary<int, int>(); // 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. if (!mp.ContainsKey(arr[i])) mp[arr[i]] = 0; mp[arr[i]]++; } // Create a Priority Queue // to sort based on the // count or on the key if the // count is same List<int> queue = mp.Keys.ToList(); queue.Sort(delegate(int y, int x) { if (mp[x] == mp[y]) return x.CompareTo(y); else return (mp[x]).CompareTo(mp[y]); }); // Print the top k elements Console.WriteLine( K + " numbers with the most occurrences are:"); for (int i = 0; i < K; i++) { Console.WriteLine(queue[i] + " "); } } // Driver's 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 phasing17 |
Javascript
// 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: ") for(let i=0; i<K; i++) { document.write(queue[i][0]+" "); }}// Driver's Codelet arr = [3, 1, 4, 4, 5, 2, 6, 1];let N = arr.length;let K = 2;// Function callprint_N_mostFrequentNumber(arr, N, K);// This code is contributed by avanitrachhadiya2155 |
Output
2 numbers with most occurrences are: 4 1
Time Complexity: O(K log D + D log D), where D is the count of distinct elements in the array.
- To remove the top of the priority queue O(log d) time is required, so if k elements are removed then O(k log d) time is required, and
- To construct a priority queue with D elements, O(D log D) time is required.
Auxiliary Space: O(D), where D is the count of distinct elements in the array.
Find K most occurring elements in the given Array using Bucket Sort
- Create a HashMap elementCount and store the count of the elements in the given array.
- Create a 2D vector frequency of size N+1 to store the elements according to their frequencies.
- Now initialize a variable count = 0.
- While count < K:
- Traverse the frequency vector from N till 0 and print the elements present in the vector and increment the count for each element.
Below is the implementation of above approach:
C++
// C++ program to find k numbers with most// occurrences in the given array#include <bits/stdc++.h>using namespace std;// Function to print the k numbers with most occurrencesvoid print_N_mostFrequentNumber(int arr[], int N, int K){ // HashMap to store count of the elements unordered_map<int, int> elementCount; for (int i = 0; i < N; i++) { elementCount[arr[i]]++; } // Array to store the elements according // to their frequency vector<vector<int> > frequency(N + 1); // Inserting elements in the frequency array for (auto element : elementCount) { frequency[element.second].push_back(element.first); } int count = 0; cout << K << " numbers with most occurrences are:\n"; for (int i = frequency.size() - 1; i >= 0; i--) { // if frequency is same,then take number with a // larger value // so,if more than 1 number present with same // frequency,then sort frequency[i] in descending // order if (frequency[i].size() > 1) { sort(frequency[i].begin(), frequency[i].end(), greater<int>()); } for (auto element : frequency[i]) { count++; cout << element << " "; // if K elements have been printed if (count >= K) return; } } return;}// Driver's codeint main(){ int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 2; // Function call print_N_mostFrequentNumber(arr, N, K); return 0;}// This code has been improved by shubhamm050402 |
Java
import java.util.*;class Main { // Function to print the k numbers with most occurrences static void print_N_mostFrequentNumber(int arr[], int N, int K) { // HashMap to store count of the elements HashMap<Integer, Integer> elementCount = new HashMap<>(); for (int i = 0; i < N; i++) { elementCount.put( arr[i], elementCount.getOrDefault(arr[i], 0) + 1); } // Array to store the elements according // to their frequency List<List<Integer> > frequency = new ArrayList<>(); for (int i = 0; i < N + 1; i++) { frequency.add(new ArrayList<>()); } // Inserting elements in the frequency array for (int element : elementCount.keySet()) { frequency.get(elementCount.get(element)) .add(element); } int count = 0; System.out.println( K + " numbers with most occurrences are: "); for (int i = frequency.size() - 1; i >= 0; i--) { // if frequency is same,then take number with a // larger value // so,if more than 1 number present with same // frequency,then sort frequency[i] in // descending order if (frequency.get(i).size() > 1) { Collections.sort( frequency.get(i), Collections.reverseOrder()); } for (int element : frequency.get(i)) { count++; System.out.print(element + " "); // if K elements have been printed if (count == K) return; } } return; } 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 shubhamm050402 |
Python3
def print_N_mostFrequentNumber(arr, N, K): # HashMap to store count of the elements count = {} # Array to store the elements according # to their frequency freq = [[] for i in range(len(arr) + 1)] for n in arr: count[n] = 1 + count.get(n, 0) for n, c in count.items(): freq.append(n) res = [] # if K elements have been printed for i in range(len(freq)-1, 0, -1): for n in freq[i]: res.append(n) if len(res) == K: return res[-1::-1]# Driver's codeif __name__ == "__main__": arr = [3, 1, 4, 4, 5, 2, 6, 1] N = len(arr) K = 2 # Function call print(print_N_mostFrequentNumber(arr, N, K)) |
C#
// C# program to find k numbers with most// occurrences in the given arrayusing System;using System.Collections.Generic;class GFG { // Function to print the k numbers with most occurrences static void print_N_mostFrequentNumber(int[] arr, int N, int K) { // HashMap to store count of the elements Dictionary<int, int> elementCount = new Dictionary<int, int>(); for (int i = 0; i < N; i++) { if (elementCount.ContainsKey(arr[i])) { elementCount[arr[i]]++; } else { elementCount.Add(arr[i], 1); } } // Array to store the elements according // to their frequency List<int>[] frequency = new List<int>[ N + 1 ]; for (int i = 0; i <= N; i++) { frequency[i] = new List<int>(); } // Inserting elements in the frequency array foreach( KeyValuePair<int, int> element in elementCount) { frequency[element.Value].Add(element.Key); } int count = 0; Console.WriteLine( K + " numbers with most occurrences are:"); for (int i = N; i >= 0; i--) { // if frequency is same,then take number with // a // larger value // so,if more than 1 number present with same // frequency,then sort frequency[i] in // descending order if (frequency[i].Count > 1) { frequency[i].Sort(); frequency[i].Reverse(); } foreach(int element in frequency[i]) { count += 1; Console.Write(element + " "); // if K elements have been printed if (count == K) return; } } return; } // Driver's code public static void Main(string[] args) { int[] arr = { 3, 1, 4, 4, 5, 2, 6, 1 }; int N = 8; int K = 2; // Function call print_N_mostFrequentNumber(arr, N, K); }}// This code is contributed by shubhamm050402 |
Javascript
// JavaScript program to find k numbers with most// occurrences in the given array// Function to print the k numbers with most occurrencesfunction print_N_mostFrequentNumber(arr, N , K){ // HashMap to store count of the elements var elementCount = new Map(); for(let i=0;i<N;i++){ if(elementCount.has(arr[i])){ var temp = elementCount.get(arr[i]); elementCount.set(arr[i], temp+1); } else{ elementCount.set(arr[i], 1); } } // Array to store the elements according // to their frequency var frequency = new Array(N+1); for(let i=0;i<=N;i++){ frequency[i] = new Array(); } // Inserting elements in the frequency array for (const [key, value] of elementCount.entries()) { frequency[value].push(key); } let count = 0; console.log(K + " numbers with most occurrences are:" + "<br>"); for(let i=N;i>=0;i--){ for(var j=frequency[i].length-1;j>=0;j--){ count++; console.log(frequency[i][j] + " "); } // if K elements have been printed if(count==K){ return; } } return;}let arr = [ 3, 1, 4, 4, 5, 2, 6, 1 ];let N = arr.length;let K = 2;// Function callprint_N_mostFrequentNumber(arr, N, K);// This code is contributed by lokeshmvs21. |
Output
2 numbers with most occurrences are: 4 1
Time Complexity: O(N logN), where N is the size of the given array. worst case is when all the elements are the same, we are sorting the entire vector.
Auxiliary Space: O(N)
Find K most occurring elements in the given Array using Quick Select:
In quick select we partition the array of unique numbers in such a way that the elements to the left of pivotpivotpivot are more frequent than pivot, and elements to the right of pivotare less frequent than pivot. Thus we can say the pivotis in its sorted position. We randomly chose such pivot until we finally find its sorted position to be K. Then we know that all the elements to the left of pivot are more frequent than pivotand each time we reduce our paritioning space w.r.t the pivot.
Partition Algorithm
Let’s imagine the pivot at store_point. If the iiith element is more frequent than pivot, then the ith element will be on the left of pivot, but the store_point is instead holding an element which is either equally or less frequent than pivot, so it should go to the right of pivot. Hence, we swap the two elements and move store_point forward so that the more frequent element is on the left. If iiith element is less frequent than pivot we assume pivot is at its right place and don’t move store_point .
At the end we swap store_point with pivot and return the sorted index.
C++
// C++ program to find k numbers with most// occurrences in the given array#include <bits/stdc++.h>using namespace std;vector<int> print_N_mostFrequentNumber(vector<int>& nums, int k, vector<int>& out){ // map for counting the number of // occurences unordered_map<int, int> counts; // stroing the frequency of each element for (int num : nums) ++counts[num]; // creating a vector for storing the // frequency vector<pair<int, int> > freqs; for (auto vt : counts) freqs.push_back({ vt.second, vt.first }); // using the user defined function // nth_element to extract the values nth_element(freqs.begin(), freqs.end() - k, freqs.end()); // using user defined function transform // to make the desired changes transform(freqs.end() - k, freqs.end(), out.begin(), [](pair<int, int> vt) { return vt.second; }); // store the result in the out vector return out;}// Driver's codeint main(){ vector<int> arr{ 3, 1, 4, 4, 5, 2, 6, 1 }; int K = 2; // Function call vector<int> ans(K); print_N_mostFrequentNumber(arr, K, ans); cout << K << " numbers with most occurences are : " << endl; for (int i = ans.size() - 1; i >= 0; i--) { cout << ans[i] << " "; } return 0;} |
Java
// JAVA program to find k numbers with most// occurrences in the given arrayimport java.util.*;class Main { static List<Integer> print_N_mostFrequentNumber(List<Integer> nums, int k, List<Integer> out) { // Map for counting the number of occurrences Map<Integer, Integer> counts = new HashMap<>(); // Storing the frequency of each element for (int num : nums) counts.put(num, counts.getOrDefault(num, 0) + 1); // Creating a list for storing the frequency List<Map.Entry<Integer, Integer> > freqs = new ArrayList<>(counts.entrySet()); // Using the user-defined function Collections.sort // to sort by frequency Collections.sort( freqs, (a, b) -> b.getValue() - a.getValue()); // Adding the k most frequent numbers to the output // list for (int i = 0; i < k; i++) out.add(freqs.get(i).getKey()); // Returning the result in the out list return out; } // Driver's code public static void main(String[] args) { List<Integer> arr = new ArrayList<>( Arrays.asList(3, 1, 4, 4, 5, 2, 6, 1)); int k = 2; // Function call List<Integer> ans = new ArrayList<>(k); print_N_mostFrequentNumber(arr, k, ans); System.out.println( k + " numbers with most occurrences are:"); for (int i = ans.size() - 1; i >= 0; i--) { System.out.print(ans.get(i) + " "); } }}// This code is contributed by shivamgupta0987654321 |
Python
# Python3 program to find k numbers with most# occurrences in the given arrayfrom collections import Counterdef print_N_mostFrequentNumber(nums, k, out): # Count the occurrences of each number counts = Counter(nums) # Get the k numbers with the highest occurrences most_frequent = counts.most_common(k) # Extract the numbers from the most frequent pairs numbers = [num for num, _ in most_frequent] # Store the numbers in the output list for i, num in enumerate(numbers): out[i] = num return out# Driver's codearr = [3, 1, 4, 4, 5, 2, 6, 1]K = 2# Function callans = [0] * Kprint_N_mostFrequentNumber(arr, K, ans)print(K, "numbers with most occurrences are:")print(ans[::-1]) |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ // Function to find k numbers with most occurrences in the given array static List<int> PrintNMostFrequentNumber(List<int> nums, int k) { // Dictionary for counting the number of occurrences Dictionary<int, int> counts = new Dictionary<int, int>(); // Storing the frequency of each element foreach (int num in nums) { if (counts.ContainsKey(num)) counts[num]++; else counts[num] = 1; } // Creating a list to store the frequency List<Tuple<int, int>> freqs = new List<Tuple<int, int>>(); foreach (var kvp in counts) { freqs.Add(new Tuple<int, int>(kvp.Value, kvp.Key)); } // Using the user-defined function (CustomNthElement) to extract the values CustomNthElement(freqs, k); // Using user-defined function Transform to make the desired changes List<int> outList = freqs.GetRange(freqs.Count - k, k).Select(t => t.Item2).ToList(); // Return the result return outList; } // Custom implementation of nth_element static void CustomNthElement(List<Tuple<int, int>> freqs, int k) { int left = 0; int right = freqs.Count - 1; while (left <= right) { int pivot = Partition(freqs, left, right); if (pivot == freqs.Count - k) return; else if (pivot < freqs.Count - k) left = pivot + 1; else right = pivot - 1; } } // Partition function for the custom nth_element static int Partition(List<Tuple<int, int>> freqs, int left, int right) { int pivot = freqs[right].Item1; int i = left; for (int j = left; j < right; j++) { if (freqs[j].Item1 <= pivot) { Swap(freqs, i, j); i++; } } Swap(freqs, i, right); return i; } // Helper function to swap elements in the list static void Swap(List<Tuple<int, int>> freqs, int i, int j) { Tuple<int, int> temp = freqs[i]; freqs[i] = freqs[j]; freqs[j] = temp; } static void Main(string[] args) { List<int> arr = new List<int> { 3, 1, 4, 4, 5, 2, 6, 1 }; int K = 2; // Function call List<int> ans = PrintNMostFrequentNumber(arr, K); Console.WriteLine(K + " numbers with most occurrences are : "); for (int i = ans.Count - 1; i >= 0; i--) { Console.Write(ans[i] + " "); } }} |
Javascript
function printNMostFrequentNumber(nums, k, out) { // Count the occurrences of each number let counts = new Map(); for (let num of nums) { counts.set(num, (counts.get(num) || 0) + 1); } // Get the k numbers with the highest occurrences let mostFrequent = Array.from(counts.entries()).sort((a, b) => b[1] - a[1]).slice(0, k); // Extract the numbers from the most frequent pairs let numbers = mostFrequent.map(([num, _]) => num); // Store the numbers in the output array for (let i = 0; i < numbers.length; i++) { out[i] = numbers[i]; } return out;}// Driver's codelet arr = [3, 1, 4, 4, 5, 2, 6, 1];let K = 2;// Function calllet ans = new Array(K).fill(0);printNMostFrequentNumber(arr, K, ans);console.log(`${K} numbers with most occurrences are:`);console.log(ans.reverse()); |
Output
2 numbers with most occurences are : 4 1
Time complexity: O(n)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
