347. Top K high-frequency elements
https://leetcode-cn.com/problems/top-k-frequent-elements/
- 347. Top K high-frequency elements
- Question description
- Method 1: Hash table
- Ideas
- Complexity analysis
- code
- Method 2: Big top pile
- Ideas
- Complexity analysis
- code
- Method 3: Small top pile
- Ideas
- Complexity analysis
- code
- Method 4: Quick selection
- Ideas
- Complexity analysis
- code
Title description
Given a non-empty integer array, return the elements with the top k highest occurrence frequencies. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] hint: You can assume that the given k is always reasonable and 1 ≤ k ≤ the number of distinct elements in the array. The time complexity of your algorithm must be better than O(n log n) , where n is the size of the array. The question data ensures that the answer is unique. In other words, the set of the first k high-frequency elements in the array is unique. You can return answers in any order. Source: LeetCode Link: https://leetcode-cn.com/problems/top-k-frequent-elements The copyright belongs to Lingkou Network. For commercial reprinting, please contact the official authorizer. For non-commercial reprinting, please indicate the source.
Method 1: Hash table
Ideas
- Traverse the array and use a hash table to count the number of times each number appears.
- Sort by number and then output the first k numbers.
Complexity analysis
- time complexity:
O
(
m
l
o
g
m
)
O(mlogm)
O(mlogm), where m is the number of distinct numbers in the array, and the maximum is N, the length of the array, which is the time of sorting.
- Space complexity:
O
(
m
)
O(m)
O(m), where m is the number of distinct numbers in the array, the space of the hash table.
Code
JavaScript Code
/**
* @param {number[]} nums
* @param {number}k
* @return {number[]}
*/
var topKFrequent = function (nums, k) {<!-- -->
// Count the number of occurrences
const map = {<!-- -->};
for (const n of nums) {<!-- -->
n in map || (map[n] = 0);
map[n] + + ;
}
// Sort the times and output the first k
returnObject.entries(map)
.sort((a, b) => b[1] - a[1])
.slice(0, k)
.map(a => a[0]);
};
Method 2: Big Top Stack
Ideas
When you see the description of top k, you can think of heap. It is better to count the number of times the number appears in the hash table, then put it into the heap and sort it by number, and then Spit out k.
Complexity analysis
- time complexity:
O
(
k
l
o
g
m
)
O(klogm)
O(klogm), m is the number of different numbers in the array, there are m elements in the heap, the time to remove the top of the heap is
l
o
g
m
logm
logm, repeated operation k times.
- Space complexity:
O
(
m
)
O(m)
O(m), where m is the number of distinct numbers in the array, the space of the hash table and the heap.
Code
JavaScript Code
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function (nums, k) {<!-- -->
// Count the number of occurrences
const map = {<!-- -->};
for (const n of nums) {<!-- -->
n in map || (map[n] = 0);
map[n] + + ;
}
//Into the heap, the format is: [number, times], sorted by times
const maxHeap = new MaxHeap(Object.entries(map), function comparator(
inserted,
compared,
) {<!-- -->
return inserted[1] < compared[1];
});
// Output the first k items
const res = [];
while (k-- > 0) {<!-- -->
res.push(maxHeap.pop()[0]);
}
return res;
};
//******************************************
class Heap {<!-- -->
constructor(list = [], comparator) {<!-- -->
this.list = list;
if (typeof comparator != 'function') {<!-- -->
this.comparator = function comparator(inserted, compared) {<!-- -->
return inserted < compared;
};
} else {<!-- -->
this.comparator = comparator;
}
this.init();
}
init() {<!-- -->
const size = this.size();
for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {<!-- -->
this.heapify(this.list, size, i);
}
}
insert(n) {<!-- -->
this.list.push(n);
const size = this.size();
for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {<!-- -->
this.heapify(this.list, size, i);
}
}
peek() {<!-- -->
return this.list[0];
}
pop() {<!-- -->
const last = this.list.pop();
if (this.size() === 0) return last;
const returnItem = this.list[0];
this.list[0] = last;
this.heapify(this.list, this.size(), 0);
return returnItem;
}
size() {<!-- -->
return this.list.length;
}
}
class MaxHeap extends Heap {<!-- -->
constructor(list, comparator) {<!-- -->
super(list, comparator);
}
heapify(arr, size, i) {<!-- -->
let largest = i;
const left = Math.floor(i * 2 + 1);
const right = Math.floor(i * 2 + 2);
if (left < size & amp; & amp; this.comparator(arr[largest], arr[left]))
largest = left;
if (right < size & amp; & amp; this.comparator(arr[largest], arr[right]))
largest = right;
if (largest !== i) {<!-- -->
[arr[largest], arr[i]] = [arr[i], arr[largest]];
this.heapify(arr, size, largest);
}
}
}
Method 3: Small top heap
Ideas
After counting the number of occurrences of each number, maintain a small top heap of size k.
Complexity analysis
- time complexity:
O
(
k
l
o
g
k
)
O(klogk)
O(klogk).
- Space complexity:
O
(
m
)
O(m)
O(m), m is the number of distinct numbers in the array, the space of the hash table, the space of the mini-max heap is
O
(
k
)
O(k)
O(k),
m >= k.
Code
JavaScript Code
/**
* @param {number[]} nums
* @param {number}k
* @return {number[]}
*/
var topKFrequent = function (nums, k) {<!-- -->
// Count the number of occurrences
const map = {<!-- -->};
for (const n of nums) {<!-- -->
n in map || (map[n] = 0);
map[n] + + ;
}
const minHeap = new MinHeap([], function comparator(inserted, compared) {<!-- -->
return inserted[1] > compared[1];
});
// Maintain a small top heap of size k. The heap element format is: [number, number of times], sorted by number of times
Object.entries(map).forEach(([num, times]) => {<!-- -->
const [, minTimes] = minHeap.peek() || [, 0];
// The size of the small top heap has not reached k, continue to insert new elements
if (minHeap.size() < k) {<!-- -->
minHeap.insert([num, times]);
}
//The size of the small top heap is k. If the number of new elements is greater than the top of the heap, pop the top of the heap and insert the new element.
// Otherwise, don't worry about this element
else if (minHeap.size() === k & amp; & amp; times > minTimes) {<!-- -->
minHeap.pop();
minHeap.insert([num, times]);
}
});
// Output all elements in the mini-max heap in reverse order
const res = Array(k);
while (k-- > 0) {<!-- -->
res[k] = minHeap.pop()[0];
}
return res;
};
//************************************
class MinHeap extends Heap {<!-- -->
constructor(list, comparator) {<!-- -->
if (typeof comparator != 'function') {<!-- -->
comparator = function comparator(inserted, compared) {<!-- -->
return inserted > compared;
};
}
super(list, comparator);
}
heapify(arr, size, i) {<!-- -->
let smallest = i;
const left = Math.floor(i * 2 + 1);
const right = Math.floor(i * 2 + 2);
if (left < size & amp; & amp; this.comparator(arr[smallest], arr[left]))
smallest = left;
if (right < size & amp; & amp; this.comparator(arr[smallest], arr[right]))
smallest = right;
if (smallest !== i) {<!-- -->
[arr[smallest], arr[i]] = [arr[i], arr[smallest]];
this.heapify(arr, size, smallest);
}
}
}
Method 4: Quick selection
Ideas
https://github.com/suukii/Articles/blob/master/articles/dsa/quick_select.md
Complexity analysis
- time complexity:
O
(
N
)
O(N)
O(N), the average is
O
(
N
)
O(N)
O(N), although theoretically the worst case is
O
(
N
2
)
O(N^2)
O(N2), but the efficiency is still good in practical applications.
- Space complexity:
O
(
N
)
O(N)
O(N), the space of the hash table is
O
(
m
)
O(m)
O(m), where m is the number of distinct numbers in the array. The worst recursive stack among quick choices should be
O
(
N
)
O(N)
O(N).
Code
JavaScript Code
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function (nums, k) {<!-- -->
// Count the number of occurrences
const map = {<!-- -->};
for (const n of nums) {<!-- -->
n in map || (map[n] = 0);
map[n] + + ;
}
const list = Object.entries(map);
quickSelect(list, k, 0, list.length - 1, function (item, pivot) {<!-- -->
return item[1] >= pivot[1];
});
return list.slice(0, k).map(el => el[0]);
};
/**
* Treat arr[r] as pivot
* Put numbers greater than or equal to pivot to the left
* Put numbers smaller than pivot to the right
* @param {number[]} arr
* @param {number} l
* @param {number} r
*/
function partition(arr, l, r, comparator) {<!-- -->
if (typeof comparator != 'function') {<!-- -->
comparator = function (num, pivot) {<!-- -->
return num >= pivot;
};
}
let i = l;
for (let j = l; j < r; j + + ) {<!-- -->
if (comparator(arr[j], arr[r])) {<!-- -->
[arr[i], arr[j]] = [arr[j], arr[i]];
i + + ;
}
}
// Change pivot to the dividing point
[arr[i], arr[r]] = [arr[r], arr[i]];
// Return the index of pivot
return i;
}
/**
* Find the kth largest element
* If the subscript of pivot happens to be k - 1, then we have found it
* If the subscript is greater than k - 1, then find the kth largest element in [left, pivotIndex - 1]
* If the subscript is less than k - 1, then find the kth - pivotIndex + left - 1 large element in the [pivotIndex + 1, right] section
* @param {number[]} list
* @param {number} left
* @param {number} right
* @param {number} k
* @param {function} comparator
*/
function quickSelect(list, k, left = 0, right = list.length - 1, comparator) {<!-- -->
if (left >= right) return list[left];
const pivotIndex = partition(list, left, right, comparator);
if (pivotIndex - left === k - 1) return list[pivotIndex];
else if (pivotIndex - left > k - 1)
return quickSelect(list, k, left, pivotIndex - 1, comparator);
else
return quickSelect(
list,
k - pivotIndex + left - 1,
pivotIndex + 1,
right,
comparator,
);
}
Summary
The above is all the content of this article. I hope it will be helpful to you and can solve the problem of the first K high-frequency elements.
If you like this article, please be sure to like, collect, comment, and forward it, it will be of great help to me. It would also be great to buy me a glass of iced Coke!
It has been completed, please continue to pay attention. See you next time~