# 0347. Top K Frequent Elements

## 刷题内容

#### 示例 1:

 输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]


#### 示例 2:

 输入: nums = [1], k = 1
输出: [1]


## 解题方案

/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
var list = {}
if (nums.length === k) {
return nums
}
while (nums.length) {
var num = nums.pop()
if (list[num]) {
list[num]++
} else {
list[num] = 1
}
}

return Object.keys(list).sort((a, b) => {
return list[b] - list[a]
}).slice(0, k).map(n => Number(n))
};


let partion = function(arr, left, right){
let i = left;
let j = right;
let base = arr[left];
while(i<j){
while(arr[j].freq<=base.freq && i<j){
j--;
}
while(arr[i].freq>=base.freq && i<j){
i++;
}
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
arr[left] = arr[i];
arr[i] = base;
return i;
}

let quickSort = function(arr, left, right, k){
if(left < right){
let m = partion(arr, left, right);
if(m<k-1){
quickSort(arr, m+1, right, k);
}else if(m>k-1){
quickSort(arr, left, m-1, k);
}
}
}

let Node = function(val, freq){
this.val = val;
this.freq = freq;
}
var topKFrequent = function(nums, k) {
let map = {};
nums.forEach(e=>{
if(map[e]){
map[e].freq += 1;
}else{
map[e] = new Node(e, 1);
}
});
let arr = [];
for(let i in map){
arr.push(map[i]);
}
quickSort(arr, 0, arr.length-1, k);
let res = [];
for(let i=0; i<k; i++){
res.push(arr[i].val);
}
return res;
};