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 8import 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 8import 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
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