说说TopK算法的各种实现

我是前端西瓜哥，今天就来讨论一下TopK算法。TopK是求数组中最小（或最大）k个数，并不要求这些数排序后返回。这是一道非常经典的面试题。解法也挺多的，可以更好的考察面试官的数据结构和算法基础。求最小值和最大值的思路是一样的，我们假设需要最小的k个数。对应的LeetCode题目地址有两个：《剑指 Offer(第 2 版)》第40题：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/《程序员面试经典(第 6 版)》17.14题目：https://leetcode-cn.com/problems/smallest-k-lcci/最简单的排序方式是全排序，即把数组的所有元素按升序排序，然后取前k个数。通常使用编程语言自带的排序API，正确性有保证。functiongetLeastNumbers(arr:number[],k:number):number[]{returnarr.sort((a,b)=>a-b).slice(0,k);};如果实际开发需求中有这个，而且数据量不大，使用内置的排序方式是最稳妥的。由于排序方法的底层通常是快速排序等时间复杂度极好的排序算法，所以全排序的时间复杂度为O(n*log(n)。在全排序的基础上，实际上，可以做一个优化，做一个部分排序。在一些算法（冒泡排序和选择排序）的排序过程中，第i次迭代将第i个元素放在最终排序的位置。下面我们看看神奇的选择排序的实现：functiongetLeastNumbers(arr:number[],k:number):number[]{letmin:number;让minIdx：数字；for(leti=0;i=hi)return;constpivot=arr[hi];//这里可以改成随机选择pivotleti=lo;for(letj=lo;jk){分区(arr,lo,i-1,k);}}functionswap(arr:number[],i:number,j:number){让tmp=arr[i];arr[i]=arr[j];arr[j]=tmp;}平均时间复杂度为O(n)，最坏时间复杂度为O(n^2)。无论如何，它通常比快速划船更有效，除非在极端情况下。大顶堆大顶堆是一棵完全二叉树，其特点是：任意一个结点的值大于或等于子树中任意一个结点的值。我们创建了一个大小为k的大顶堆。先放k个元素。后面要放新元素的时候，先和堆顶元素（堆的最大值）比较。如果小于堆的最大元素，说明堆顶元素不合格，不能成为TopK的成员，将其从堆中移除，将新元素放入堆中；否则，新元素不会被放入堆中。继续这样做，直到遍历整个数组。最后一个堆就是我们想要的TopK。JavaScript没有内置堆或优先队列等数据结构，所以暂时不去实现。入堆时间复杂度为O(logk)，需要入堆n次，所以总时间复杂度为O(n*logk)。如果需要动态维护TopK，比如网站的每日排行榜，使用bigtopheap方案比较合适。综上所述，一般来说，快排思路时间复杂度最低，大顶堆适合需要动态维护TopK的情况，全排适合写业务代码和量大的情况数据不大。