Top K Frequent Elements
Problem
Given an array of integer and integer K, our task is to find the K most frequent elements in the Array. The K most frequent elements can be in any order.
For example,
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Explanation: The 2 most frequent elements are [1,2]. [2,1] is also a valid output because the output doesn't have to be sorted.
Input: nums = [1], k = 1
Output: 1
Explanation: The 1 most frequent elements is only 1.
Solution
Priority Queue (Heap)
fun topKFrequent(nums: IntArray, k: Int): IntArray {
val map = mutableMapOf<Int, Int>()
nums.forEach {
map[it] = map.getOrDefault(it, 0) + 1
}
val priorityQueue = PriorityQueue<Pair<Int, Int>>(
compareByDescending { it.second }
)
map.forEach {
priorityQueue.add(Pair(first = it.key, second = it.value))
}
val result = IntArray(k)
var i = 0
while (i < k && priorityQueue.isNotEmpty()) {
result[i] = priorityQueue.remove().first
i++
}
return result
}class ElementFrequency {
private int element;
private int frequency;
public ElementFrequency(int element, int frequency) {
this.element = element;
this.frequency = frequency;
}
public int getFrequency() {
return this.frequency;
}
}
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
PriorityQueue<ElementFrequency> priorityQueue = new PriorityQueue<>(
Comparator.comparing(ElementFrequency::getFrequency).reversed()
);
map.forEach((key, value) -> {
priorityQueue.add(new ElementFrequency(key, value));
}
);
int[] result = new int[k];
int i = 0;
while (i < k && !priorityQueue.isEmpty()) {
result[i] = priorityQueue.remove().element;
i++;
}
return result;
}Quickselect
fun topKFrequent(nums: IntArray, k: Int): IntArray {
val map = mutableMapOf<Int, Int>()
nums.forEach {
map[it] = map.getOrDefault(it, 0) + 1
}
val arr = Array<Pair<Int, Int>>(map.size) { Pair(first = 0, second = 0) }
var i = 0
map.forEach {
arr[i] = Pair(first = it.key, second = it.value)
i++
}
quickSelect(arr, map.size - k, 0, map.size - 1)
val result = IntArray(k)
i = 0
while (i < k) {
result[i] = arr[arr.size - 1 - i].first
i++
}
return result
}
private fun quickSelect(nums: Array<Pair<Int, Int>>, k: Int, low: Int, high: Int) {
if (low == high) return
val position: Int = hoarePartition(nums, low, high)
return if (k <= position) quickSelect(nums, k, low, position) else quickSelect(nums, k, position + 1, high)
}
private fun hoarePartition(nums: Array<Pair<Int, Int>>, low: Int, high: Int): Int {
val pivot = nums[(low + high) / 2].second
var i = low - 1
var j = high + 1
while (true) {
do {
i++
} while (nums[i].second < pivot)
do {
j--
} while (nums[j].second > pivot)
if (i >= j) return j
nums[i] = nums[j].also {
nums[j] = nums[i]
}
}
}class ElementFrequency {
private int element;
private int frequency;
public ElementFrequency(int element, int frequency) {
this.element = element;
this.frequency = frequency;
}
public int getFrequency() {
return this.frequency;
}
}
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
ElementFrequency[] arr = new ElementFrequency[map.size()];
int i = 0;
for (Integer key : map.keySet()) {
arr[i] = new ElementFrequency(key, map.get(key));
i++;
}
quickSelect(arr, map.size() - k, 0, map.size() - 1);
int[] result = new int[k];
i = 0;
while (i < k) {
result[i] = arr[arr.length - 1 - i].element;
i++;
}
return result;
}
private void quickSelect(ElementFrequency[] nums, int k, int low, int high) {
if (low == high) return;
int position = hoarePartition(nums, low, high);
if (k <= position)
quickSelect(nums, k, low, position);
else
quickSelect(nums, k, position + 1, high);
}
private int hoarePartition(ElementFrequency[] nums, int low, int high) {
int pivot = nums[(low + high) / 2].frequency;
int i = low - 1;
int j = high + 1;
while (true) {
do {
i++;
} while (nums[i].frequency < pivot);
do {
j--;
} while (nums[j].frequency > pivot);
if (i >= j) return j;
ElementFrequency temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}Bucket Sort
fun topKFrequent(nums: IntArray, k: Int): IntArray {
var min = nums[0]
var max = nums[0]
for (num in nums) {
if (num > max) max = num else if (num < min) min = num
}
val frequencies = IntArray(max - min + 1)
for (num in nums) {
frequencies[num - min]++
}
val buckets = arrayOfNulls<ArrayList<Int>>(nums.size + 1)
for (i in frequencies.indices) {
val num = i + min
val frequency = frequencies[i]
if (buckets[frequency] == null) {
buckets[frequency] = ArrayList()
}
buckets[frequency]!!.add(num)
}
var k = k
val result = IntArray(k)
var i = buckets.size - 1
while (k > 0) {
buckets[i]?.let {
for (num in buckets[i]!!) {
k -= 1;
result[k] = num;
if (k == 0) {
break;
}
}
}
i--
}
return result
}public int[] topKFrequent(int[] nums, int k) {
int min = nums[0], max = nums[0];
for (int num : nums) {
if (num > max)
max = num;
else if (num < min)
min = num;
}
int[] frequencies = new int[max - min + 1];
for (int num : nums) {
frequencies[num - min]++;
}
List<Integer>[] buckets = new List[nums.length + 1];
for (int i = 0; i < frequencies.length; i++) {
int num = i + min;
int frequency = frequencies[i];
if (buckets[frequency] == null) {
buckets[frequency] = new ArrayList<>();
}
buckets[frequency].add(num);
}
int[] result = new int[k];
for (int i = buckets.length - 1; k > 0; i--) {
if (buckets[i] != null) {
for (int num : buckets[i]) {
k -= 1;
result[k] = num;
if (k == 0) {
break;
}
}
}
}
return result;
}