力扣347题-前 K 个高频元素

题目

十分暴力的方法，没想到竟然没超时

var topKFrequent = function(nums, k) {
  const map = new Map();
  for(let props of nums){
    const temp = map.get(props);
    map.set(props, !temp?1:temp+1);
  }
  const map2 = new Map();
  const arr = [];
  const arr2 = [];
  map.forEach((item, key)=>{
    arr.push(item);
    arr2.push(key);
  })
  for(let i=arr.length-1;i>=0;i--){
    for(let j=1;j<=i;j++){
      if(arr[j]>arr[j-1]){
        [arr[j],arr[j-1]] = [arr[j-1],arr[j]];
        [arr2[j],arr2[j-1]] = [arr2[j-1],arr2[j]];
      }
    }
  }
  return arr2.slice(0,k);
};

本来想优化一下嘞，结果时间更长了。

var topKFrequent = function(nums, k) {
  const map = new Map();
  const map2 = new Map();
  const result = [];
  for(let props of nums){
    const temp = map.get(props);
    const num = !temp ? 1 : temp+1;
    map.set(props, num);
    if(!temp){
      result.push(props);
      map2.set(props, result.length-1);
    }else{
      let idx = map2.get(props);
      while(idx!==0&&num>map.get(result[idx-1])){
        [result[idx], result[idx-1]] = [result[idx-1], result[idx]];
        map2.set(result[idx], idx);
        idx--;
      }
      map2.set(props, idx);
    }
  }
  return result.slice(0,k);
};

优化了一下，思路和第一种差不多，我以前一直想排序map来着，可以不太会，今天终于会了。

var topKFrequent = function(nums, k) {
  let map = new Map();
  for(let num of nums){
    map.set(num, map.has(num) ? map.get(num)+1 : 1);
  }
  if(k === map.size)return [...map.keys()];
  let arr = Array.from(map).sort((a,b)=>b[1]-a[1]);
  return arr.slice(0,k).map(n => n[0]);
};