topK问题

最大/小的 K 个数，第 K 个最大/最小值

• 局部冒泡
  ！！输出结果无序

  function bubbleSort(arr, k) {
    for (let i = 0; i < k; i++) {
      // 冒泡执行k次
      for (let j = arr.length - 1; j > i; j--) {
        if (arr[j] < arr[j - 1]) {
          [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
        }
      }
    }
  }
  // K相当于冒泡次数
  //前k个小值
  data.slice(0, k);
  //第k小的值
  data[k - 1];

• 堆排序

// topk
function heapObj(items,k){
  const heap = [,...items.slice(0,k)]
  const heapSize = k
  buildHeap(heap,heapSize)

  // 求大值，建立最小堆
  // 后续与最小堆堆顶比较
  for(let j = k ; j < items.length ; j++){
    if(heap[1] < items[j]){
      // 如果大于最小
      // 作为堆顶的新值，调整堆
      heap[1] = items[j]
      heapify(heap,heapSize,1)
    }
  }
  return heap.slice(1)
  // 前k个大值
}
function buildHeap(items,heapSize){
  if(heapSize === 1) return
  for(let i = Math.floor(heapSize/2) ; i > 0 ; i --){
    heapify(items,heapSize,i)
  }
}
function heapify(items,heapSize,i){
  while(true){
    let minIndex = i
    if(2*i <= heapSize && items[2*i] < items[i]) minIndex = 2*i
    if(2*i+1 <= heapSize && items[2*i+1] < items[minIndex]) minIndex = 2*i+1
    if(minIndex===i) break
    [items[i],items[minIndex]] = [items[minIndex],items[i]]
    i = minIndex
  }
}

• 快速选择

  快排的改装

  // 第k大的元素
  function quickSort(arr,k){
    return quick(arr,0,arr.length-1,k)
  
    function quick(arr,l,r,k){
      const index = partition(arr,l,r)
      // 这里开始和一般快排不同
      // 第k大的值，索引为k-1
      // partition选出的位置与这个k比较
      // 根据pivot与k-1的相对位置，每次只用继续partition一半
      if(index === k-1){
        return arr[index]
      }
      if(index > k-1){
        return quick(arr,l,index-1,k)
      }
      if(index < k-1){
        return quick(arr,index+1,r,k)
      }
    }
  }
  
  function partition(arr,l,r){
    const pivot = arr[r]
    let i = l
    for(let j = l;j<r;j++){
      if(arr[j]<pivot){
        [arr[j],arr[i]] = [arr[i],arr[j]]
        i++
      }
    }
    [arr[i],arr[r]] = [arr[r],arr[i]]
    return i 
  }
  

出现最多/最少的 K 个元素

• 傻瓜 map 映射一个 arr 进行排序

function showMost(arr, k) {
  const map = new Map();
  const ret = [...new Set(arr)];

  arr.map((num) => {
    if (map.has(num)) {
      map.set(num, map.get(num) + 1);
    } else {
      map.set(num, 1);
    }
  });

  ret.sort((a, b) => map.get(b) - map.get(a));
  return ret.slice(0, k);
}

• map 映射堆排序

function showMost(arr, k) {
  const map = new Map();
  const heap = [,];
  arr.map((num) => {
    if (map.has(num)) {
      map.set(num, map.get(num) + 1);
    } else {
      map.set(num, 1);
    }
  });
  if (map.size <= k) return [...map.keys()];
  //k大于元素数，直接输出
  let times = 1;
  //记数器
  //小于k的部分直接建立堆，大于的部分开始与堆top比较
  map.forEach((value, key) => {
    if (times <= k) {
      heap.push(key);
      if (times === k) {
        //堆化
        buildHeap(heap, map, k);
      }
    } else if (map.get(heap[1]) < value) {
      // 与小顶堆顶交换
      heap[1] = key;
      heapify(heap, map, k, 1);
    }
    times++;
  });
  function buildHeap(heap, map, heapSize) {
    if (k === 1) return;
    for (let i = Math.floor(heapSize / 2); i >= 1; i--) {
      heapify(heap, map, heapSize, i);
    }
  }
  function heapify(heap, map, heapSize, i) {
    while (true) {
      let minIndex = i;
      if (2 * i <= heapSize && map.get(heap[2 * i]) < map.get(heap[minIndex]))
        minIndex = 2 * i;
      if (
        2 * i + 1 <= heapSize &&
        map.get(heap[2 * i + 1]) < map.get(heap[minIndex])
      )
        minIndex = 2 * i + 1;
      if (minIndex === i) break;
      swap(heap, minIndex, i);
      i = minIndex;
    }
  }
  heap.shift();
  return heap;
}
function swap(data, l, r) {
  let temp = data[l];
  data[l] = data[r];
  data[r] = temp;
}

• 桶排序

出现次数最多的前k个数

function showMost(arr,k){
  // 记录各数字出现次数
  const map = new Map()
  arr.map((num) => {
    if (map.has(num)) {
      map.set(num, map.get(num) + 1);
    } else {
      map.set(num, 1);
    }
  });
  if(map.size<=k) return [...map.keys()]
  return buckerSort(map,k)
}

function buckerSort(map,k){
  // 按照出现次数作为arr数组下标划分桶
  // 将数字放入桶中
  let arr = []
  let res = []
  map.forEach((value,key)=>{
    if(!arr[value]){
      arr[value] = [key]
    }else{
      arr[value].push(key)
    }
    // 出现了value次的数字有...
  })
  // 逆向遍历桶数组
  // 
  for(let i = arr.length - 1 ; i>=0 && res.length < k ; i--){
    // 从出现最多的数字开始收集直到收集到k个
    if(arr[i]){
      res.push(...arr[i])
    }
  }
  return res
}