Top K问题

1、TopK是什么

从长度为N的无序数组中找出前k大的数，这就是所谓的Top k问题

2、分析解决

之所以这个问题比较经典，原因在于这个数组的长度太大（超过1亿），以至于无法一次下放到内存中进行排序，所以才会被人研究。

2.1、hash

使用hash的作用是减少重复数量，但是要注意的是，题目求的是排位是第K大的数还是求第K大个数字

如果是前者我们就不可以使用hash来降低数据规模

2.2、堆

使用堆这样的数据结构可以在内存消耗为K时解决此问题，一般来说：

• 对于求前K大，我们用小顶堆，前K小的话用大顶堆

对于前者问题分析：

• 建立一个大小为K的小顶堆
• 将K个元素入堆
• 然后将剩下的（n - K）个元素一个一个判断
  • 如果元素比堆顶大，则将堆顶pop，入堆
  • 如果元素比堆顶小，continue

由此我们就可以在空间复杂度为O(K)，时间复杂度为O(n)求出答案

import java.util.*;

// NC-119
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> ans = new ArrayList<>();
        if(input.length < k || input.length == 0 || k == 0) return ans;
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> (b - a));
        for(int i = 0; i < input.length; i++) {
            // heap.add(input[i]);
            if(heap.size() < k) {
                heap.add(input[i]);
            } else if(input[i] < heap.peek()){
                heap.poll();
                heap.add(input[i]);
            }
        }
        for(int j = 0; j < k; j++) {
            ans.add(heap.poll());
        }
        Collections.reverse(ans);
        return ans;
    }
}

2.3、快速排序法

再使用快排的时候，我们的步骤一般是：

• 选出pivot
• 将小于pivot的元素放在pivot左边
• 将大于pivot的元素放在pivot右边

于是我们可以想到：

• 如果在某一次执行完快排时发现pivot的索引位置正好为K-1，则前面的数字正好就是答案
• 如果发现pivot的索引位置小于K-1，则我们需要往右边找
• 如果发现pivot的索引位置大于K-1，则我们只需往左边找

于是利用这种思想，我们就可以做到

import java.util.*;

public class Solution {
    
    // NC-88
    public int findKth(int[] a, int K) {
        if(a.length == 0 || K == 0) return 0;
        return quickSort(a, K);
    }
    
    private int quickSort(int[] arr, int K) {
        Deque<int[]> stack = new LinkedList<>();
        int[] arrNode = {0, arr.length - 1};
        stack.push(arrNode);

        while (!stack.isEmpty()) {
            int[] node = stack.pop();
            // if(node[0] >= node[1]) continue;
            int left = node[0], right = node[1], pivot = arr[left];
            while(left < right) {
                // 右
                while (left < right) {
                    if (arr[right] > pivot) {
                        right--;
                    } else {
                        arr[left] = arr[right];
                        left++;
                        break;
                    }
                }
                // 左
                while (left < right) {
                    if (arr[left] < pivot) {
                        left++;
                    } else {
                        arr[right] = arr[left];
                        right--;
                        break;
                    }
                }
            }
            arr[left] = pivot;
            if(left == K - 1) {
                return arr[left];
            } else if(left < K - 1) {
                stack.push(new int[]{left + 1, node[1]});
            } else {
                stack.push(new int[]{node[0], left - 1});
            }
        }
        return 0;
    }

}

2.4、分治

在进行以上堆或者快排执行时候，整个时间复杂度在数据规模太大的情况下依然不是很满意

于是我们可以将整个亿级别的数据规模分为几个区，在区中用如上方法找出每个区中的TopK的值，再对每个区中的K的元素进行合并，找出最后的TopK，不同分区可以多线程并发执行，由此来降低我们的时间