topK问题

import com.again.common.arithmetic.Sort.HeapSort;
import com.google.common.base.Preconditions;

import java.util.Arrays;

/**
 * TopK问题：在指定数据中查找最大(或最小)的k个数。
 */
public class TopK {

    /**
     * 打印出数组中最小的k个数
     *
     * 优点：时间复杂度为O(n)
     * 缺点：改变了原数组中元素的位置
     *
     * @param array
     * @param k
     */
    public static void getLeastElements(int[] array, int k) {

        Preconditions.checkArgument(null != array && k > 0 && array.length > k);

        int left = 0;
        int right = array.length - 1;

        int indexOfK = k - 1;

        Partition.makePivotIndexEqualsK(array, left, right, indexOfK);

        for (int i = 0; i <= indexOfK; i++) {
            Partition.print(array[i]);
        }
    }


    /**
     * 打印出数组中最大的k个数
     *
     * 优点：时间复杂度为O(n)
     * 缺点：改变了原数组中元素的位置
     *
     * @param array
     * @param k
     */
    public static void getLargestElements(int[] array, int k) {

        Preconditions.checkArgument(null != array && k > 0 && array.length > k);

        int left = 0;
        int right = array.length - 1;

        int indexOfK = array.length - k;

        Partition.makePivotIndexEqualsK(array, left, right, indexOfK);

        for (int i = indexOfK; i < array.length; i++) {
            Partition.print(array[i]);
        }
    }


    /**
     * 打印出数组中最小的k个数
     *
     * 思路：
     *  1)创建一个大小为k的辅助数组来存储数组中最小的k个数，用数组的前k个元素来初始化辅助数组。
     *  2)使用堆排序来对辅助数组进行排序，故排序后，辅助数组的最后一个元素即最大值。
     *  3)从数组的第k+1个元素开始遍历数组，若遍历的元素小于辅助数组中的最大值，则将辅助数组中的最大值替换为当前遍历的元素。
     *
     * 时间复杂度为O(nlogk)
     *      遍历的数组的时间复杂度为O(n)
	 *		对长度为k的辅助数组进行排序的时间复杂度为O(klogk)，这里我们并不需要对辅助数组的k个元素都进行排序，我们只需要将k个元素中个的最大值放到辅助数组的最后一个位置即可(即排序时只调整一次即可)，故时间复杂度为O(logk)
     *      故：总的时间复杂度 = O(n)*O(logk) = O(nlogk)
     *      
     * 优点：
     *  1)不需要改变数组中元素的位置。
     *  2)适合在海量数据中查找topk：
     *      1>若输入的数据量很大，则很可能无法一次性将所有的数据都加载到内存中，此时就无法利用Partition函数来求topk的问题了。
     *      2>若输入的数据量很大，我们每次从输入源(eg：文件)中获取一个数字，然后对该数字进行判断即可。故这种方式仅仅要求内存能容纳下 一个大小为k的辅助数组 即可。
     *
     * @param array
     * @param k
     */
    public static void getLeastElementsByHeapSort(int[] array, int k) {

        Preconditions.checkArgument(null != array && k > 0 && array.length > k);

        // 用数组的前k个元素来初始化辅助数组
        int[] heapArray = Arrays.copyOfRange(array, 0, k);

        // 使用堆排序来对辅助数组进行排序
        HeapSort heapSort = new HeapSort();
        heapSort.sort(heapArray);

        // 从数组的第k+1个元素开始遍历数组，若遍历的元素小于辅助数组中的最大值，则将辅助数组中的最大值替换为当前遍历的元素。
        for (int i = k; i < array.length; i++) {
            if (array[i] < heapArray[k - 1]) {
                heapArray[k - 1] = array[i];
                heapSort.sort(heapArray);
            }
        }
        System.out.println(Arrays.toString(heapArray));
    }


    public static void main(String[] args) {


        int[] array = {55, 2, 3, 4, 5, 6, 7, 8, 1, 9};
        getLeastElementsByHeapSort(array, 5);
        getLeastElements(array, 5);

        System.out.println("");
    }

}