topK

1. 问题描述

TopK Elements 问题用于找出一组数中最大的 K 个的数。

此外还有一种叫 Kth Element 问题，用于找出一组数中第 K 大的数。

如果要找的 TopK Elements 是最小的 K 个数，那么可以将问题转换成求解 TopK Elements，因为找到 Kth Element 之后，再遍历一遍，小于等于 Kth Element 的数都是 TopK Elements。

2. 一般解法

以 Leetcode : 215. Kth Largest Element in an Array 为例，这是一道的 Kth Element 问题，不过这道题要找的是从后往前第 K 个元素，而不是从前往后。为了能和传统的 Kth Element 问题一样求解，可以先执行 k = nums.length - k;

Input: [3,2,1,5,6,4] and k = 2
Output: 5

2.1 快速选择

快速排序的 partition() 方法，对于数组 nums 的 [l, h] 区间，会返回一个整数 k 使得 nums[l…k-1] 小于等于 nums[k]，且 nums[k+1…h] 大于等于 nums[k]，此时 nums[k] 就是数组的第 k 大元素。可以利用这个特性找出数组的 Kth Element，这种找 Kth Element 的算法称为快速选择算法。

• 时间复杂度 O(N)、空间复杂度 O(1)
• 只有当允许修改数组元素时才可以使用

public int findKthElement(int[] nums, int k) {
    k = nums.length - k;
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int j = partition(nums, l, h);
        if (j == k) {
            break;
        } else if (j < k) {
            l = j + 1;
        } else {
            h = j - 1;
        }
    }
    return nums[k];
}

private int partition(int[] a, int l, int h) {
    int i = l, j = h + 1;
    while (true) {
        while (a[++i] < a[l] && i < h) ;
        while (a[--j] > a[l] && j > l) ;
        if (i >= j) {
            break;
        }
        swap(a, i, j);
    }
    swap(a, l, j);
    return j;
}

private void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

2.2 堆

维护一个大小为 K 的最小堆，堆顶元素就是 Kth Element。

使用大顶堆来维护最小堆，而不能直接创建一个小顶堆并设置一个大小，企图让小顶堆中的元素都是最小元素。

维护一个大小为 K 的最小堆过程如下：在添加一个元素之后，如果大顶堆的大小大于 K，那么需要将大顶堆的堆顶元素去除。

• 时间复杂度 O(NlogK) 、空间复杂度 O(K)
• 特别适合处理海量数据

在下面的实现中，令 k = nums.length - k + 1;，这是因为此时 k 不是从零开始，和上面的快速选择解法有所不同。

public int findKthLargest(int[] nums, int k) {
    k = nums.length - k + 1;
    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); // 大顶堆
    for (int val : nums) {
        pq.add(val);
        if (pq.size() > k)  // 维护堆的大小为 K
            pq.poll();
    }
    return pq.peek();
}

3. 海量数据

在这种场景下，单机通常不能存放下所有数据。

• 拆分，可以按照哈希取模方式拆分到多台机器上，并在每个机器上维护最大堆；
• 整合，将每台机器得到的最大堆合并成最终的最大堆。

4. 频率统计

Heavy Hitters 问题要求找出一个数据流的最频繁出现的 K 个数，比如热门搜索词汇等。

4.1 HashMap

使用 HashMap 进行频率统计，然后使用快速选择或者堆的方式找出频率 TopK。在海量数据场景下，也是使用先拆分再整合的方式来解决空间问题。

4.2 Count-Min Sketch

维护 d*w 大小的二维统计数组，其中 d 是哈希函数的个数，w 根据情况而定。

• 在一个数到来时，计算 d 个哈希值，然后分别将哈希值对 w 取模，把对应统计数组上的值加 1；
• 要得到一个数的频率，也是要计算 d 个哈希值并取模，得到 d 个频率，取其中最小值。

该算法的思想和布隆过滤器类似，具有一定的误差，特别是当 w 很小时。但是它能够在单机环境下解决海量数据的频率统计问题。

public class CountMinSketch {

    private int d;
    private int w;

    private long estimators[][];

    public CountMinSketch(int d, int w) {
        this.d = d;
        this.w = w;
    }

    public void add(int value) {
        for (int i = 0; i < d; i++)
            estimators[i][hash(value, i)]++;
    }

    public long estimateFrequency(int value) {
        long minimum = Integer.MAX_VALUE;
        for (int i = 0; i < d; i++) {
            minimum = Math.min(minimum, estimators[i][hash(value, i)]);
        }
        return minimum;
    }

    private int hash(int value, int i) {
        return 0; // use ith hash function
    }
}

4.3 Trie

Trie 树可以用于解决词频统计问题，只要在词汇对应节点保存出现的频率。它很好地适应海量数据场景，因为 Trie 树通常不高，需要的空间不会很大。

什么是Topk问题

其实顾名思义，这个问题也就是在N个数中找出前k个最值。在我们的日常生活中，很多地方都有Topk问题的影子，例如我们在点外卖时，总会说这家店是某某市的多少名，其实这些都是用Topk问题的解决方法得出来的。

方法一：堆排序法

这也是最容易想到的一种方法：我们可以将N个数排成有序的，然后输出前k个最值，而在我们已学过的排序算法中，堆排序的时间复杂度又是最快的（O（n*logn）），因此我们选择了堆排序。

//交换函数
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//堆的向下调整（小堆）
void AdjustDown(int* a, int n, int parent)
{
	//child记录左右孩子中值较小的孩子的下标
	int child = 2 * parent + 1;//先默认其左孩子的值较小
	while (child < n)
	{
		if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小
		{
			child++;//较小的孩子改为右孩子
		}
		if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小
		{
			//将父结点与较小的子结点交换
			Swap(&a[child], &a[parent]);
			//继续向下进行调整
			parent = child;
			child = 2 * parent + 1;
		}
		else//已成堆
		{
			break;
		}
	}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
	*returnSize = k;
	int i = 0;
	//建小堆
	for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, arrSize, i);
	}
	//排降序
	int end = arrSize - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
	//将最大的k个数存入数组
	int* retArr = (int*)malloc(sizeof(int)*k);
	for (i = 0; i < k; i++)
	{
		retArr[i] = arr[i];
	}
	return retArr;//返回最大的k个数
}

时间复杂度：O(N+NlogN) 空间复杂度：O(N)，能否将其再优化了？肯定是可以的，下面看方法二。

方法二：把N个数建堆，取出前k个

这种方法其实也不难想到，我们利用了堆的性质：堆的0号位一定是最值，小堆则为最小值，大堆则为最大值。

注意点：
1.取出数据后要让其与最后的元素替换，因为你已经取出这个元素了，所以不需要它了，这时让它去堆尾，不让它算入堆的个数中就行了。为什么要这样做了，因为这样既保证了堆的结构，也相当于把这个取出来的数删除了。
2. 如果在取到堆顶数据后直接删除数据，那么就要重新建堆了。正确的做法应该是上面所说的方法，因为那样只要进行一次向下调整，就可以保证堆的结构了。要知道建堆的复杂度为O(N),而一次向下调整的复杂度仅为O（logn），这样大大提升了效率。

//交换函数
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//堆的向下调整（大堆）
void AdjustDown(int* a, int n, int parent)
{
	//child记录左右孩子中值较大的孩子的下标
	int child = 2 * parent + 1;//先默认其左孩子的值较大
	while (child < n)
	{
		if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在并且右孩子比左孩子还大
		{
			child++;//较大的孩子改为右孩子
		}
		if (a[child] > a[parent])//左右孩子中较大孩子的值比父结点还大
		{
			//将父结点与较大的子结点交换
			Swap(&a[child], &a[parent]);
			//继续向下进行调整
			parent = child;
			child = 2 * parent + 1;
		}
		else//已成堆
		{
			break;
		}
	}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
	*returnSize = k;
	int i = 0;
	//建大堆
	for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, arrSize, i);
	}
	//将最大的k个数存入数组
	int* retArr = (int*)malloc(sizeof(int)*k);
	int end = arrSize - 1;
	for (i = 0; i < k; i++)
	{
		retArr[i] = arr[0];//取堆顶数据
		Swap(&arr[0], &arr[end]);//交换堆顶数据与最后一个数据
		//进行一次向下调整，不把最后一个数据看作待调整的数据，所以待调整数据为end=arrSize-1
		AdjustDown(arr, end, 0);
		end--;//最后一个数据的下标改变
	}
	return retArr;//返回最大的k个数
}

时间复杂度：O（n+k*logn），空间复杂度：O（n），那么问题来了，万一n是一个特别大的数字了，那效率依旧不是很高，有没有更快的方法了？下面我们来看看方法三。

方法三：建一个k个数的堆

我们以找出最大的k个数为例，该方法为：先建一个k个数的小堆，然后将数组中n-k个元素依次与堆顶的元素比较，若比堆顶元素大，则将堆顶元素删除，然后将这个数插入到堆中，这儿要注意：插入这个数到堆中的时候，要使用向上排序算法保证堆的结构不被破坏。到最后，堆里面的k个数就是最大的k个数了。

那么问题来了，上面的例子中为什么不用大堆了，不是选最大的k个数吗？其实这很容易理解，我们假设一下，如果建一个大堆，万一堆顶的数据就是n个数中最大的那个，那么不论怎么比较，你后面的n-k个元素都没法进堆，因此要用小堆来解决这个问题。

void PrintTopK(int* a, int n, int k)
{
	Hp hp;
	HpInit(&hp, a, k);
	int i = k;
	for (i = k; i < n; i++)
	{
		if (a[i]>HpTop(hp))
		{
			HpPop(&hp);
			HpPush(&hp, a[i]);
		}
	}
	//你此时数据改变之后是在堆里面的，你打印a没用啊
	//for (i = 0; i < k; i++)
	//{
	//	printf("%d ", a[i]);
	//}
	for (i = 0; i < k; i++)
	{
		printf("%d ", HpTop(hp));
		HpPop(&hp);
	}
	printf("\n");
}

时间复杂度：O（k+n*logk） 空间复杂度：O（n） 与之前两种方法对比，这种方法大大提高了效率。

TopK问题三种方法总结

Top K问题的两种解决思路

TOP-K问题的几种解法

Top-K问题的几种求解方法

快速选择排序 Quick select 解决Top K 问题

what’s topK?

topK问题是实际应用中涉及面较广的一个抽象问题，譬如：从20亿个数字的文本中，找出最大的前100个。

堆

具体可以参考我的另一篇文章：数据结构javascript描述中对于heap的总结。

解题步骤

• 首先把数组中的前k个值用来建一个小根堆(不是大根堆)。
• 之后的其他数拿到之后进行判断，如果遇到比小顶堆的堆顶的值大的，将堆顶元素删除，将该元素放入堆中
• 最终的堆会是数组中最大的K个数组成的结构，小根堆的顶部又是结构中的最小数，因此把堆顶的值弹出即可得到Top-K。

具体实现

// 注意如果求的不是topK而是lowK则是用 大根堆
import Heap from './algorithm/Heap/MinHeap';
const topK=(arr,k)=>{
    let h=new Heap();
    for(let i=0;i<k;i++){
        h.insert(arr[i]);
    }
    for(let i=k;i<arr.length;i++){
        if (arr[i]>h.data[0]){
            h.deleting();
            h.insert(arr[i]);
        }
    }
    return h.data[0];
};

summary

• 时间复杂度： O(NlogK)其中N为数组全部长度，K即为要求的K（因为堆中元素的数目永远是K）

quickSelect

解题步骤

• swap函数交换元素位置
• partition 按照快排的分割思想，pivot左边是比pivot小的所有数，返回pivot所在位置
• 核查pivot-left+1和k大小比较
  • 如果大于k那么topK就在pivot左侧的这些数里面
  • 如果等于k那么topK就是pivot所在位置的值
  • 如果小于k那么寻找pivot右侧的topk-(pivot-left+1)即可

具体实现

const swap=(arr,a,b)=>{
    let temp=arr[a];
    arr[a]=arr[b];
    arr[b]=temp;
};
const partition=(arr,k,left,right)=>{
    let pivot=left,lessThan=left;
    if(left===right) return left;
    for(let i=left;i<=right;i++){
        if(arr[i]<arr[pivot]){
            lessThan++;
            swap(arr,lessThan,i);
        }
    }
    swap(arr,lessThan,pivot);
    return lessThan;
};
const quickSelect=(arr,k,left,right)=>{
    let idx=partition(arr,k,left,right);
    // 一定要注意：idx已经被检查过所以不能再将其加入重新进行检查
    if(right-idx+1>k){
        return quickSelect(arr,k,idx+1,right);
    }else if(right-idx+1===k){
        return arr[idx];
    }else{
        return quickSelect(arr,k-(right-idx+1),left,idx-1);
    }
};
const topK=(arr,k)=>{
    return quickSelect(arr,k,0,arr.length-1);
};

summary

quickSelect方法 与Quick sort不同的是，Quick select只考虑所寻找的目标所在的那一部分子数组，而非像Quick sort一样分别再对两边进行分 割。正是因为如此，Quick select将平均时间复杂度从O(nlogn)降到了O(n),但与此同时，QuickSelect与QuickSort一样，是一个不稳定的算法；pivot选取直接影响了算法的好坏，worst case下的时间复杂度达到了O(n^2)

• 时间复杂度最大为:O(n^2)
• 时间复杂度最小为:O(n)
• 空间复杂度:O(1)

二分法

关于二分查找法的详解可以参考我的另一篇文章：详解二分查找法

解题步骤

• 找到最大值max和最小值min
• 计算mid值开始循环查找
  • 注意我们的max可以等于min，因为max min均为数组中的值
  • 如果比mid大的数目大于等于k，那么mid过小，min变成mid+1
    • 为什么要把等于k的情况加入呢，因为等于k的情况下，选取的mid是小于等于目标值的
  • 如果比mid大的数目小于k，那么mid过大，max变成mid-1
• 返回max值即为我们想要的

具体实现

const topK2=(arr,k)=>{
    let low=Number.MAX_SAFE_INTEGER,high=-Number.MAX_SAFE_INTEGER;
    for(let i=0;i<arr.length;i++){
        if(arr[i]<low){
            low=arr[i];
        }
        if(arr[i]>high){
            high=arr[i];
        }
    }
    // count用来计算从大于mid小于high的数字的个数
    let cn;
    while(low<=high){
        let mid=Math.floor((low+high)/2);
        cn=count(arr,mid);
        // console.info('===>',{low,high},cn,mid);
        if(cn>=k){
            // mid is too small
            low=mid+1;
        }else{
            // mid is too big
            high=mid-1;
        }
    }
    return high;
};




// =========>扩展
/**
 * 如何改造成求最小的第k个值呢
 * @param arr
 * @param k
 * @returns {number}
 */
const topK3=(arr,k)=>{
    const count1=(arr,target)=>{
        let count=0;
        for(let i=0;i<arr.length;i++){
            if(arr[i]<=target){
                count++;
            }
        }
        return count;
    };
    let low=Number.MAX_SAFE_INTEGER,high=-Number.MAX_SAFE_INTEGER;
    for(let i=0;i<arr.length;i++){
        if(arr[i]<low){
            low=arr[i];
        }
        if(arr[i]>high){
            high=arr[i];
        }
    }
    // count用来计算从大于mid小于high的数字的个数
    let cn;
    while(low<=high){
        let mid=Math.floor((low+high)/2);
        cn=count1(arr,mid);
        // console.info('===>',{low,high},cn,mid);
        if(cn>=k){
            // mid is too big
            high=mid-1;
        }else{
            // mid is too small
            low=mid+1;
        }
    }
    return low;
};

summary

• 时间复杂度：O(nlog(max-min)) （不确定）
• 空间复杂度：O(1)

leetcode-719-找出第 k 小的距离对

首先这个题就是典型的topk问题，但是用构建最大堆的方式并不能通过，因此这边可以考虑用二分法的方式解决，既然采用二分法套用上面模板即可，但是难点在于如何遍历所有找出来小于mid的所有距离对的个数呢？（遍历所有显然不现实）

此处查找count数目用到了双指针:

• 维护一个right 递增
• 查找一个最小的left满足arr[right]-arr[left]<=mid
• 叠加right-left的值即为小于mid的所有距离对个数。(至于为何是right-left可以通过自己举例验证比如1到4之间有多少距离对：3+2+1)

const count=(arr,target)=>{
    let res=0,left=0;
    for(let right=0;right<arr.length;right++){
        while(arr[right]-arr[left]>target)left++;
        res+=right-left;
    }
    return res;
};
const smallestDistancePair1=(arr,k)=>{
    arr.sort((a,b)=>a-b);
    let min=0,max=arr[arr.length-1]-arr[0];
    while(min<=max){
        let mid=Math.floor((min+max)/2);
        let cn=count(arr,mid);
        if(cn>=k){
            // mid过大,===k的情况时有可能取的mid也是一个大于目标值的数
            max=mid-1;
        }else{
            min=mid+1;
        }
    }
    return min;
};

leetcode-378-有序矩阵中第K小的元素

解题思路可以参考我的题解二分法解决or最小堆解决（此处不赘述）