Find k numbers with most occurrences in the given Python array

In this tutorial, we shall find k numbers with most occurrences in the given Python array. The inputs shall be the length of the array, its elements, and a positive integer k. We should find k numbers that occur the highest number of times in the given array. These k numbers should have the highest frequency. If the number k is larger than the number of elements with maximum frequency, the numbers are returned in decreasing order of frequency. The larger number comes first if the numbers are of the same frequency.

Input: arr[] = [7, 1, 1, 4, 6, 2, 7, 3], k = 2
Output: 7 1

Explanation:
Frequency of 7 = 2
Frequency of 1 = 2
These two have the maximum frequency and 7 > 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, 11 = 2, 7 = 2, 10 = 1 
Since 11 > 7, 11 is printed before 7

Implementation

First, We shall create an empty dictionary and enter its key-value pair as the number-frequency pair. After traversing through all the elements of arr, the dictionary dct now contains the numbers and their frequencies. Next, we copy these values to another empty list a which contains the key-value pairs as individual lists.

First, we sort the list in decreasing order of number so that all numbers are arranged according to high-value priority. Secondly, we again sort the list in decreasing order of frequency value so that the highest frequency lists come first. Print the first k numbers.

Below is our Python program to find k numbers with most occurrences in the given array:

def kFrequentNumbers(arr, n, k): 
  dct = {} 
  for i in range(n): #key = number and value = frequency
    if arr[i] in dct: 
      dct[arr[i]] += 1
    else: 
      dct[arr[i]] = 1

  a = [0] * (len(dct)) 
  j = 0
  for i in dct: 
    a[j] = [i, dct[i]] #a[j][0] has number and a[j][1] has frequency
    j += 1
  a = sorted(a, key = lambda x : x[0], reverse = True) #sorts in dec. order of number
  a = sorted(a, key = lambda x : x[1], reverse = True) #sorts in dec. order of frequency
            
  # display the top k numbers 
  print(k, "numbers with most occurrences are:") 
  for i in range(k): 
    print(a[i][0], end = " ") #prints top k numbers

# Driver code 
if __name__ =="__main__": 
  arr = []
  n = int(input("Enter the length of the array: "))
  print("Enter elements: ")
  for i in range(n):
    e = int(input())
    arr.append(e)
  k = int(input("Enter k: "))
  kFrequentNumbers(arr, n, k)

Implementation Example for the sorted() functions above:
For arr = [3, 1, 4, 4, 5, 2, 6, 1]
Now, a = [[3,1],[1,2],[4,2],[5,1],[2,1],[6,1]]
After first sorted() -> a = [[6,1],[5,1],[4,2],[3,1],[2,1],[1,2]]
And after second sorted() -> a = [[4,2],[1,2],[6,1],[5,1],[3,1],[2,1]]
If k=3, Using a[i][0] gives the first 3 numbers which are 4, 1, 6

Output:
Enter the length of the array: 11
Enter elements:
7 10 11 5 2 5 5 7 11 8 9
Enter k: 4
4 numbers with most occurrences are:
5 11 7 10

I am Vamsi Krishna and You can find my other posts here:

Find bitonic point in given bitonic sequence in Python
Get all possible sublists of a list in Python

Also Read:
Track the occurrences of a character in a string in Python
How to Construct an array from its pair-sum array in Python

Thank You for Reading and Keep Learning 🙂

Leave a Reply