如何实现TopK问题的解决方案？之快速选择实现

TopK问题是指在一个数据集合中，找出排名前K的元素。常见的解决方案有两种：堆排序和快速选择。

快速选择

快速选择是一种基于快速排序的算法，它通过分治的思想，快速定位排名第K大的元素。首先，选择一个元素作为枢纽元素，然后将整个数据集合分为两个部分，大于枢纽元素的部分和小于枢纽元素的部分。如果小于枢纽元素的部分数量小于K，那么就在大于枢纽元素的部分中找第K-smallest个元素；否则，就在小于枢纽元素的部分中找第K个元素。

下面是TopK问题的Java实现：

public class TopK {
    public static int[] topK(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        while (true) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == k - 1) {
                break;
            } else if (pivotIndex < k - 1) {
                left = pivotIndex + 1;
            } else {
                right = pivotIndex - 1;
            }
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = nums[i];
        }
        return result;
    }

    private static int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] < pivot) {
                j--;
            }
            nums[i] = nums[j];
            while (i < j && nums[i] >= pivot) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = pivot;
        return i;
    }
}