0347. Top K Frequent Elements

难度: Medium

刷题内容

原题连接

• https://leetcode-cn.com/problems/top-k-frequent-elements/

内容描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

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

示例 2:

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

解题方案

思路 1
**- 时间复杂度: O(N*k)**- 空间复杂度: 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(N*k)**- 空间复杂度: 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;
};