Skip to main content

Top k frequent elements in array

Here given code implementation process.

// Java Program 
// Top k frequent elements in array
import java.util.HashMap;
import java.util.ArrayList;
public class Frequency
{
    public void kthFrequent(int[] arr, int n, int k)
    {
        if (k < 1 || n < 1)
        {
            // Invalid inputs
            return;
        }
        // Use to collect element frequency
        HashMap < Integer, Integer > record = 
          new HashMap < Integer, Integer > ();
        // Use to combine elements by frequency  
        HashMap < Integer, ArrayList < Integer > > result = 
          new HashMap < Integer, ArrayList < Integer > > ();
        // Find the frequency of array element
        for (int i = 0; i < n; ++i)
        {
            if (record.containsKey(arr[i]))
            {
                // When element exist
                // Increase the element frequency
                record.put(arr[i], record.get(arr[i]) + 1);
            }
            else
            {
                // Add new record
                record.put(arr[i], 1);
            }
        }
        // Combine elements by frequency
        for (int key: record.keySet())
        {
            if (result.containsKey(record.get(key)) == false)
            {
                result.put(record.get(key), new ArrayList < Integer > ());
            }
            result.get(record.get(key)).add(key);
        }
        System.out.print("\n Initial " + k + " Frequent Element is \n");
        // Use to collect key
        int[] keyRecord = new int[result.size()];
        int count = 0;
        // Get key in array
        for (int key: result.keySet())
        {
            keyRecord[count] = key;
            count++;
        }
        count = 0;
        // iterates the loop through by key Record in reverse order
        for (int j = result.size() - 1; j >= 0; j--)
        {
            // Get resultant node
            ArrayList < Integer > ans = result.get(keyRecord[j]);
            // Display calculate element
            for (int data: ans)
            {
                System.out.print("  " + data);
                count++;
                if (count >= k)
                {
                    return;
                }
            }
        }
    }
    public static void main(String[] args)
    {
        Frequency task = new Frequency();
        int[] arr = {
            5 , 8 , 9 , 7 , 9 , 2 , 9 , 8 , 5 , 9 , 5 , 8
        };
        int k = 3;
        int n = arr.length;
        task.kthFrequent(arr, n, k);
    }
}

Output

 Initial 3 Frequent Element is
  9  5  8
// Include header file
#include <iostream>
#include <unordered_map>
#include <map>
#include <vector>
using namespace std;

// C++ Program
// Top k frequent elements in array

class Frequency
{
    public: void kthFrequent(int arr[], int n, int k)
    {
        // Invalid inputs
        if (k < 1 || n < 1)
        {
            return;
        }
        // Use to collect element frequency
        unordered_map < int, int > record;
        // Use to combine elements by frequency
        map < int, vector < int > > result ;
        // Find the frequency of array element
        for (int i = 0; i < n; ++i)
        {
            if (record.find(arr[i]) != record.end())
            {
                // When element exist
                // Increase the element frequency
                record[arr[i]] = record[arr[i]] + 1;
            }
            else
            {
                // Add new record
                record[arr[i]] = 1;
            }
        }
        for (auto &info: record)
        {
            result[info.second].push_back(info.first);
        }
        cout << "\n Initial " << k << " Frequent Element is \n";
        // Use to collect key
        int *keyRecord = new int[result.size()];
        int count = 0;
        for (auto &info: result)
        {
            keyRecord[count] = info.first;
            count++;
        }
        count = 0;
        // iterates the loop through by key Record in reverse order
        for (int j = result.size() - 1; j >= 0; j--)
        {
            // Get resultant node
            vector < int > ans = result[keyRecord[j]];
            for (vector<int>::iterator data = ans.begin(); data != ans.end(); data++)
            {
                cout << "  " << *data;
                count++;
                if (count >= k)
                {
                    return;
                }
            }
        }
    }
};
int main()
{
    Frequency task = Frequency();
    int arr[] = {
        5 , 8 , 9 , 7 , 9 , 2 , 9 , 8 , 5 , 9 , 5 , 8
    };
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    task.kthFrequent(arr, n, k);
    return 0;
}

Output

 Initial 3 Frequent Element is
  9  5  8
// Include namespace system
using System;
using System.Collections.Generic;
// C# Program
// Top k frequent elements in array
public class Frequency
{
    public void kthFrequent(int[] arr, int n, int k)
    {
        // Invalid inputs
        if (k < 1 || n < 1)
        {
            return;
        }
        // Use to collect element frequency
        Dictionary < int, int > record = 
          new Dictionary < int, int > ();
        // Use to combine elements by frequency
        Dictionary < int, List < int > > result = 
          new Dictionary < int, List < int > > ();
        // Find the frequency of array element
        for (int i = 0; i < n; ++i)
        {
            if (record.ContainsKey(arr[i]))
            {
                // When element exist
                // Increase the element frequency
                record[arr[i]] = record[arr[i]] + 1;
            }
            else
            {
                // Add new record
                record.Add(arr[i], 1);
            }
        }
        foreach(KeyValuePair < int, int > info in record)
        {
            if (result.ContainsKey(info.Value) == false)
            {
                result.Add(info.Value, new List < int > ());
            }
            result[info.Value].Add(info.Key);
        }
        Console.Write("\n Initial " + k + " Frequent Element is \n");
        // Use to collect key
        int[] keyRecord = new int[result.Count];
        int count = 0;
        foreach(KeyValuePair < int,  List < int > > info in result)
        {
            keyRecord[count] = info.Key;
            count++;
        }
        Array.Sort(keyRecord); 
        count = 0;
        // iterates the loop through by key Record in reverse order
        for (int j = result.Count - 1; j >= 0; j--)
        {
            // Get resultant node
            List < int > ans = result[keyRecord[j]];
            foreach(int data in ans)
            {
                Console.Write("  " + data);
                count++;
                if (count >= k)
                {
                    return;
                }
            }
        }
    }
    public static void Main(String[] args)
    {
        Frequency task = new Frequency();
        int[] arr = {
            5 , 8 , 9 , 7 , 9 , 2 , 9 , 8 , 5 , 9 , 5 , 8
        };
        int k = 3;
        int n = arr.Length;
        task.kthFrequent(arr, n, k);
    }
}

Output

 Initial 3 Frequent Element is
  9  5  8
<?php
// Php Program
// Top k frequent elements in array
class Frequency
{
    public  function kthFrequent( & $arr, $n, $k)
    {
        // Invalid inputs
        if ($k < 1 || $n < 1)
        {
            return;
        }
        // Use to collect element frequency
        $record = array();
        // Use to combine elements by frequency
        $result = array();
        // Find the frequency of array element
        for ($i = 0; $i < $n; ++$i)
        {
            if (array_key_exists($arr[$i], $record))
            { // When element exist
                // Increase the element frequency
                $record[$arr[$i]] = $record[$arr[$i]] + 1;
            }
            else
            { // Add new record
                $record[$arr[$i]] = 1;
            }
        }
        foreach($record as $key => $value)
        {
            if (array_key_exists($record[$key], $result) == false)
            {
                $result[$record[$key]] = array();
            }
            $result[$record[$key]][] = $key;
        }
        echo "\n Initial ". $k ." Frequent Element is \n";
        // Use to collect key
        $keyRecord = array_fill(0, count($result), 0);
        $count = 0;
      
        ksort($result);
      
        foreach($result as $key => $value)
        {
            $keyRecord[$count] = $key;
            $count++;
        }
        $count = 0;
        // iterates the loop through by key Record in reverse order
        for ($j = count($result) - 1; $j >= 0; $j--)
        {
            // Get resultant node
            $ans = $result[$keyRecord[$j]];
            foreach($ans as $data)
            {
                echo "  ". $data;
                $count++;
                if ($count >= $k)
                {
                    return;
                }
            }
        }
    }
}

function main()
{
    $task = new Frequency();
    $arr = array(5, 8, 9, 7, 9, 2, 9, 8, 5, 9, 5, 8);
    $k = 3;
    $n = count($arr);
    $task->kthFrequent($arr, $n, $k);
}
main();

Output

 Initial 3 Frequent Element is
  9  5  8
// Node Js Program
// Top k frequent elements in array
class Frequency
{
    kthFrequent(arr, n, k)
    {
        // Invalid inputs
        if (k < 1 || n < 1)
        {
            return;
        }
        // Use to collect element frequency
        var record = new Map();
        // Use to combine elements by frequency
        var result = new Map();
        // Find the frequency of array element
        for (var i = 0; i < n; ++i)
        {
            if (record.has(arr[i]))
            {
                // When element exist
                // Increase the element frequency
                record.set(arr[i], record.get(arr[i]) + 1);
            }
            else
            {
                // Add new record
                record.set(arr[i], 1);
            }
        }
        for (let [key, value] of record)
        {
            if (result.has(value) == false)
            {
                result.set(record.get(key), []);
            }
            result.get(value).push(key);
        }
        console.log("\n Initial " + k + " Frequent Element is ");
        // Use to collect key
        var keyRecord = Array(result.size).fill(0);
        // Sort map by key
        result = new Map([...result.entries()].sort());
        var count = 0;
        for (let [key, value] of result)
        {
            keyRecord[count] = key;
            count++;
        }
        count = 0;
        // iterates the loop through by key Record in reverse order
        for (var j = result.size - 1; j >= 0; j--)
        {
            // Get resultant node
            var ans = result.get(keyRecord[j]);
            for (let data of ans)
            {
                process.stdout.write("  " + data);
                count++;
                if (count >= k)
                {
                    return;
                }
            }
        }
    }
}

function main()
{
    var task = new Frequency();
    var arr = [5, 8, 9, 7, 9, 2, 9, 8, 5, 9, 5, 8];
    var k = 3;
    var n = arr.length;
    task.kthFrequent(arr, n, k);
}
main();

Output

 Initial 3 Frequent Element is
  9  5  8
#  Python 3 Program
#  Top k frequent elements in array
class Frequency :
    def kthFrequent(self, arr, n, k) :
        #  Invalid inputs
        if (k < 1 or n < 1) :
            return
        
        #  Use to collect element frequency
        record = dict()
        #  Use to combine elements by frequency
        result = dict()
        #  Find the frequency of list element
        i = 0
        while (i < n) :
            if (arr[i] in record.keys()) :
                #  When element exist
                #  Increase the element frequency
                record[arr[i]] = record.get(arr[i]) + 1
            else :
                #  Add new record
                record[arr[i]] = 1
            
            i += 1
        
        for key, value in record.items() :
            if ((value in result.keys()) == False) :
                result[value] = []
            
            result.get(value).append(key)
        
        print("\n Initial", k ,"Frequent Element is ")
        #  Use to collect key
        keyRecord = [0] * (len(result))
        count = 0
        
        for key, value in result.items() :
            keyRecord[count] = key
            count += 1

        keyRecord.sort()

        count = 0
        #  iterates the loop through by key Record in reverse order
        j = len(result) - 1
        while (j >= 0) :
            #  Get resultant node
            ans = result.get(keyRecord[j])
            for data in ans :
                print("  ", data, end = "")
                count += 1
                if (count >= k) :
                    return
            j -= 1


def main() :
    task = Frequency()
    arr = [5, 8, 9, 7, 9, 2, 9, 8, 5, 9, 5, 8]
    k = 3
    n = len(arr)
    task.kthFrequent(arr, n, k)

if __name__ == "__main__": main()

Output

 Initial 3 Frequent Element is
   9   8   5
#  Ruby Program
#  Top k frequent elements in array
class Frequency 
    def kthFrequent(arr, n, k) 
        #  Invalid inputs
        if (k < 1 || n < 1) 
            return
        end

        #  Use to collect element frequency
        record = Hash.new 
        #  Use to combine elements by frequency
        result = Hash.new
        #  Find the frequency of array element
        i = 0
        while (i < n) 
            if (record.key?(arr[i])) 
                record[arr[i]] = record[arr[i]] + 1
            else 
                record[arr[i]] = 1
            end

            i += 1
        end

        record.each { | key, value | 
            if (result.key?(value) == false) 
                result[value] = []
            end

            result[value].push(key)
        }
        # sort hash by key
        result = result.sort.to_h
        print("\n Initial ", k ," Frequent Element is \n")
        #  Use to collect key
        keyRecord = Array.new(result.size()) {0}
        count = 0
        result.each { | key, value | 
            keyRecord[count] = key
           count += 1
        }
        count = 0
        #  iterates the loop through by key Record in reverse order
        j = result.size() - 1
        while (j >= 0) 
            #  Get resultant node
            ans = result[keyRecord[j]]
            for data in ans do 
                print("  ", data)
                count += 1
                if (count >= k) 
                    return
                end
            end
            j -= 1
        end
    end
end

def main() 
    task = Frequency.new()
    arr = [5, 8, 9, 7, 9, 2, 9, 8, 5, 9, 5, 8]
    k = 3
    n = arr.length
    task.kthFrequent(arr, n, k)
end

main()

Output

 Initial 3 Frequent Element is 
  9  5  8
import scala.collection.mutable._;
// Scala Program
// Top k frequent elements in array
class Frequency
{
    def kthFrequent(arr: Array[Int], n: Int, k: Int): Unit = {
        // Invalid inputs
        if (k < 1 || n < 1)
        {
            return;
        }
        // Use to collect element frequency
        
        var record = Map[Int, Int]();
        // Use to combine elements by frequency
        var result = Map[Int,  ArrayBuffer[Int]]();
        // Find the frequency of array element
        var i: Int = 0;
        while (i < n)
        {
            if (record.contains(arr(i)))
            {
                // When element exist
                // Increase the element frequency
                record.addOne(arr(i), record.get(arr(i)).get + 1);
            }
            else
            {
                // Add new record
                record.addOne(arr(i), 1);
            }
            i += 1;
        }
        for ((k, v) <- record)
        {
            if (result.contains(v) == false)
            {
                result.addOne(v, new ArrayBuffer[Int]());
            }
            result.get(v).get.append(k);
        }
        print("\n Initial " + k + " Frequent Element is \n");
        // Use to collect key
        var keyRecord: Array[Int] = Array.fill[Int](result.size)(0);
        var count: Int = 0;
        for ((k, v) <- result)
        {
            keyRecord(count) = k;
            count += 1;
        }
        count = 0;
        var j: Int = result.size - 1;
        // iterates the loop through by key Record in reverse order
        while (j >= 0)
        {
            // Get resultant node
            var ans = result.get(keyRecord(j)).get;
            for (data <- ans)
            {
                print("  " + data);
                count += 1;
                if (count >= k)
                {
                    return;
                }
            }
            j -= 1;
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var task: Frequency = new Frequency();
        var arr: Array[Int] = Array(5, 8, 9, 7, 9, 2, 9, 8, 5, 9, 5, 8);
        var k: Int = 3;
        var n: Int = arr.length;
        task.kthFrequent(arr, n, k);
    }
}

Output

 Initial 3 Frequent Element is
  9  5  8
import Foundation
// Swift 4 Program
// Top k frequent elements in array
class Frequency
{
    func kthFrequent(_ arr: [Int], _ n: Int, _ k: Int)
    {
        // Invalid inputs
        if (k < 1 || n < 1)
        {
            return;
        }
        // Use to collect element frequency
        var record = [Int: Int]();
        // Use to combine elements by frequency
        var result = [Int: [Int]]();
        // Find the frequency of array element
        var i: Int = 0;
        while (i < n)
        {
            if (record.keys.contains(arr[i]))
            {
                // When element exist
                // Increase the element frequency
                record[arr[i]] = record[arr[i]]! + 1;
            }
            else
            {
                // Add new record
                record[arr[i]] = 1;
            }
            i += 1;
        }
        for (key, value) in record
        {
            if (result.keys.contains(value) == false)
            {
                result[value] = [Int]();
            }
            result[value]!.append(key);
        }
        print("\n Initial ", k ," Frequent Element is ");
        // Use to collect key
        var keyRecord: [Int] = Array(repeating: 0, count: result.count);
        let temp = result.sorted { $0.0 < $1.0 };
        var count: Int = 0;
        for (key, _) in temp
        {
            keyRecord[count] = key;
            count += 1;
        }
        count = 0;
        // iterates the loop through by key Record in reverse order
        var j: Int = result.count - 1;
        while (j >= 0)
        {
            
            // Get resultant node
            let ans = result[keyRecord[j]]!;
            for data in ans
            {
                print("  ", data, terminator: "");
                count += 1;
                if (count >= k)
                {
                    return;
                }
            }
            j -= 1;
        }
    }
}
func main()
{
    let task: Frequency = Frequency();
    let arr: [Int] = [5, 8, 9, 7, 9, 2, 9, 8, 5, 9, 5, 8];
    let k: Int = 3;
    let n: Int = arr.count;
    task.kthFrequent(arr, n, k);
}
main();

Output

 Initial  3  Frequent Element is
   9   5   8
// Kotlin Program
// Top k frequent elements in array
class Frequency
{
    fun kthFrequent(arr: Array < Int > , n: Int, k: Int): Unit
    {
        // Invalid inputs
        if (k < 1 || n < 1)
        {
            return;
        }
        // Use to collect element frequency
        var record = mutableMapOf<Int, Int>();
        // Use to combine elements by frequency
        var result = mutableMapOf<Int, ArrayList <Int> >();
        // Find the frequency of array element
        var i: Int = 0;
        while (i < n)
        {
            if (record.containsKey(arr[i]))
            {
                // When element exist
                // Increase the element frequency
                record.put(arr[i], record.getValue(arr[i]) + 1);
            }
            else
            {
                // Add new record
                record.put(arr[i], 1);
            }
            i += 1;
        }
        // Combine elements by frequency
        for (key in record.keys)
        {
            if (result.containsKey(record.getValue(key)) == false)
            {
                result.put(record.getValue(key), ArrayList <Int> ());
            }
            result.getValue(record.getValue(key)).add(key);
        }
        print("\n Initial " + k + " Frequent Element is \n");
        // Use to collect key
        var keyRecord: Array < Int > = Array(result.count())
        {
            0
        };
        var count: Int = 0;
        // Get key in array
        for (key in result.keys)
        {
            keyRecord[count] = key;
            count += 1;
        }
        keyRecord.sort();
        count = 0;
        // iterates the loop through by key Record in reverse order
        var j: Int = result.count() - 1;
        while (j >= 0)
        {
            // Get resultant node
            
            var ans = result.getValue(keyRecord[j]);
            // Display calculate element
            for(data in ans)
            {
                print("  " + data);
                count += 1;
                if (count >= k)
                {
                    return;
                }
            }
            j -= 1;
        }
    }
}
fun main(args: Array < String > ): Unit
{
    var task: Frequency = Frequency();
    var arr: Array < Int > = arrayOf(5, 8, 9, 7, 9, 2, 9, 8, 5, 9, 5, 8);
    var k: Int = 3;
    var n: Int = arr.count();
    task.kthFrequent(arr, n, k);
}

Output

 Initial 3 Frequent Element is
  9  5  8
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment