[LeetCode] #347. Top K Frequent Elements
題目
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
1 <= nums.length <= 105kis in the range[1, the number of unique elements in the array].It is guaranteed that the answer is unique.
直覺解
構想：
紀錄每個數字出現幾次，依照出現次數由大至小排序，取出前 k 個數字。
javascript 實作：
const topKFrequent = function(nums, k) {
if (nums.length === k) { return nums }
let numsDisplayCount = {}
const result = []
for (const num of nums) {
if (!numsDisplayCount[num]) {
numsDisplayCount[num] = 1
} else {
numsDisplayCount[num]++
}
}
numsDisplayCount = Object.entries(numsDisplayCount).sort((a, b) => b[1] - a[1])
for (let i = 0; i < k; i++) {
result.push(numsDisplayCount[i][0])
}
return result
}
效能：
Runtime: 96 ms, faster than 61.59% of JavaScript online submissions for Top K Frequent Elements.
Memory Usage: 42.6 MB, less than 40.57% of JavaScript online submissions for Top K Frequent Elements.
尚未更正的錯誤：
- 對 object 使用 array.sort 方法。雖然最後算出來的答案正確，但總覺得毛毛的⋯⋯
研究別人的解
來源：
[javascript] [hash map] [max heap] [priority queue] solution
別人的 javascript 實作：
var topKFrequent = function(nums, k) {
// results array
let results = [];
// 1) first step is to build a hash map, where "element -> its frequency"
// it costs O(n), where n is nums.length
let map = {};
nums.forEach(n => map[n] ? map[n] += 1 : map[n] = 1);
let pq = new PriorityQueue();
// 2) enqueue each map element to max binary heap priority queue
for(let key in map){
// it costs O(log n), where n is nums.length
pq.enqueue(key, map[key]);
}
// 3) k times dequeue element from priority queue and push it to results array
for(let i = 0; i < k; i++){
// it costs O(log n), where n is nums.length
results.push(pq.dequeue());
}
// return results array
// as result we have O(n Log n) where n is length of nums
return results;
};
class PriorityQueue {
constructor(){
this._values = [];
}
enqueue(val, priority){
this._values.push(new Node(val, priority));
this._traverseUp();
}
dequeue(){
const max = this._values[0];
const end = this._values.pop();
if(this._values.length > 0){
this._values[0] = end;
this._traverseDown();
}
return max.val;
}
_traverseUp(){
let idx = this._values.length - 1;
const el = this._values[idx];
while(idx > 0){
let pIdx = Math.floor((idx - 1) / 2);
let parent = this._values[pIdx];
if(el.priority <= parent.priority) break;
this._values[pIdx] = el;
this._values[idx] = parent;
idx = pIdx;
}
}
_traverseDown(){
let leftChildIdx = null;
let rightChildIdx = null;
let leftChild = null;
let rightChild = null;
let swapIdx = null;
let idx = 0
const el = this._values[idx];
while(true){
swapIdx = null;
leftChildIdx = 2 * idx + 1;
rightChildIdx = 2 * idx + 2;
if(leftChildIdx < this._values.length){
leftChild = this._values[leftChildIdx];
if(leftChild.priority > el.priority){
swapIdx = leftChildIdx;
}
}
if(rightChildIdx < this._values.length){
rightChild = this._values[rightChildIdx];
if(
(swapIdx === null && rightChild.priority > el.priority) ||
(swapIdx !==null && rightChild.priority > leftChild.priority)
) {
swapIdx = rightChildIdx;
}
}
if(swapIdx === null) break;
this._values[idx] = this._values[swapIdx];
this._values[swapIdx] = el;
idx = swapIdx
}
}
}
class Node {
constructor(val, priority){
this.val = val;
this.priority = priority;
}
}
效能：
Runtime: 96 ms, faster than 64.51% of JavaScript online submissions for Top K Frequent Elements.
Memory Usage: 41.8 MB, less than 64.03% of JavaScript online submissions for Top K Frequent Elements.
研究過程：
class Node {
constructor(val, priority){
this.val = val;
this.priority = priority;
}
}
定義 node 節點。預計用途：this.val 存的是數字，this.priority 存的是這個數字出現幾次（節點在 heap 中的排列方式：次數多的排前面，少的排後面）。
class PriorityQueue：
constructor(){
this._values = [];
}
用陣列實作 heap。陣列的 index 和 heap 的排列結構，對應方式是：父節點的 index 是 k 的話，兩個子節點的 index 分別是 2*k+1 和 2*k+2。反過來說，子節點的 index 是 k 的話，父節點的 index 是 Math.floor((k - 1) / 2)
enqueue(val, priority){
this._values.push(new Node(val, priority));
this._traverseUp();
}
把新的節點加進 heap：先建立新的 node，再把 node 加進 heap 的最後面。如果新加入的 node 優先性比較高，就把他往前排。
dequeue(){
const max = this._values[0];
const end = this._values.pop();
if(this._values.length > 0){
this._values[0] = end;
this._traverseDown();
}
return max.val;
}
用途：從 heap 裡面拿出排在最前面的元素。
實作方式：把排在最前面的元素存到 max，把排在最後面的元素移除，並存在 end 裡。如果移除一個元素後， 沒有變成空陣列的話，用 end 把「排在最前面的元素的值」覆蓋掉，這樣可以確保 heap 已經移除了該「排在最前面的元素」。不過這麼做以後，變成優先性最低的元素排在最前面，所以要重新排列 heap。
_traverseUp(){
let idx = this._values.length - 1;
const el = this._values[idx];
while(idx > 0){
let pIdx = Math.floor((idx - 1) / 2);
let parent = this._values[pIdx];
if(el.priority <= parent.priority) break;
this._values[pIdx] = el;
this._values[idx] = parent;
idx = pIdx;
}
}
用途：優先性高的元素要排到前面。
實作方式：從 heap 的最後一個元素開始，檢查子元素的 priority 是否有比父元素的 priority 小，沒有的話就把兩個節點交換。
_traverseDown(){
let leftChildIdx = null;
let rightChildIdx = null;
let leftChild = null;
let rightChild = null;
let swapIdx = null;
let idx = 0
const el = this._values[idx];
while(true){
swapIdx = null;
leftChildIdx = 2 * idx + 1;
rightChildIdx = 2 * idx + 2;
if(leftChildIdx < this._values.length){
leftChild = this._values[leftChildIdx];
if(leftChild.priority > el.priority){
swapIdx = leftChildIdx;
}
}
if(rightChildIdx < this._values.length){
rightChild = this._values[rightChildIdx];
if(
(swapIdx === null && rightChild.priority > el.priority) ||
(swapIdx !==null && rightChild.priority > leftChild.priority)
) {
swapIdx = rightChildIdx;
}
}
if(swapIdx === null) break;
this._values[idx] = this._values[swapIdx];
this._values[swapIdx] = el;
idx = swapIdx
}
}
用途：優先性低的元素要排到後面。
實作方式：從 heap 的第一個元素開始，檢查是否符合「父元素的 priority > 兩個子元素的 priority」，沒有的話就把父節點和「兩個子節點中 priority 比較大的那個（平手的話，選左邊節點）」交換。
參考資料
Comments
Post a Comment