0347. Top K Frequent Elements
难度: Medium
刷题内容
原题连接
内容描述
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
解题方案
思路 1 *- 时间复杂度: O(Nk)*- 空间复杂度: O(N)***
利用原生的sort方法， 1. 遍历原有数组，推导出每个数字出现的频率。 2. 根据出现的频率，利用sort进行排序
代码：
/**
* @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))
};
思路 2 *- 时间复杂度: O(Nk)*- 空间复杂度: O(N)***
自行实现的排序方式 1. 遍历原有数组，推导出每个数字出现的频率。 2. 利用快排实现排序
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;
};
