一天一大 lee(前 K 个高频元素)难度:中等-Day20200907

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

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

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  let map = new Map(),
    arr = []
  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i])) {
      let val = map.get(nums[i])
      map.set(nums[i], ++val)
    } else {
      map.set(nums[i], 1)
      arr.push(nums[i])
    }
  }
  let sortArr = arr.sort((a, b) => map.get(b) - map.get(a))
  return sortArr.splice(0, k)
}

var topKFrequent = function (nums, k) {
  let map = new Map(),
    heap = [],
    arr = []

  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i])) {
      let val = map.get(nums[i])
      map.set(nums[i], ++val)
    } else {
      map.set(nums[i], 1)
      arr.push(nums[i])
    }
  }

  if (map.size <= k) return arr

  for (let [key, value] of map) {
    if (heap.length < k) {
      heap.push(key)
      // 堆内放够k个元素后，对前k个元素堆化（即根据出现频率从小到大排列）
      buildHeapIn(heap.length - 1);
    } else if (map.get(heap[0]) < value) {
      // 出现大于堆顶的元素则替换掉对顶，并且重新对新的堆排序
      heap[0] = key
      buildHeapOut(0); 
    }
  }

  // 添加元素重新排序
  function buildHeapIn(x) {
    while (x > 0) {
      let y =  parseInt((x - 1)/2,10); 
      if (map.get(heap[y]) > map.get(heap[x])) { 
        swap(heap,y, x);
        x = y;
      } else {
        break;
      }
    }
  }

  // 替换元素重新排序
  function buildHeapOut(x) {
    while (2 * x + 1 < heap.length) {
      let y = 2 * x + 1;
      if (y + 1 < heap.length && map.get(heap[y+1]) < map.get(heap[y])) { 
        y++;
      }
      if ( map.get(heap[x]) > map.get(heap[y])) {
        swap(heap,x, y);
        x = y; 
      } else {
        break;
      }
    }
  }

  // 替换元素
  function swap(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
  }
  return heap.reverse()
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = (nums, k) => {
  let map = new Map(),
    heap = [],
    arr = [],
    _result = []
  ValueKey = [];

  // 哈希
  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i])) {
      let val = map.get(nums[i])
      map.set(nums[i], ++val)
    } else {
      map.set(nums[i], 1)
      arr.push(nums[i])
    }
  }

  if (map.size <= k) return arr

  // 索引
  for (let [key, value] of map) {
    if (!ValueKey[value]) {
      ValueKey[value] = [key];
    } else {
      ValueKey[value].push(key)
    }
  }

  // 从后向其取k个元素
  for (let i = ValueKey.length - 1; i >= 0; i--) {
    if (_result.length < k && ValueKey[i]) {
      _result = _result.concat(ValueKey[i])
    } else {
      continue
    }
  }
  return _result;
};