TopK 问题-白红宇

问题描述

Top K问题指给你一堆数据，求最大或者最小的前几个。例如：1000w个数字，求最大的100个。

解法

1.最小（大）堆

利用小（大）顶堆绝对是最好的办法。原理：先从1000w个数据里取100个，构建小顶堆。接下来就遍历所有的数据，遇到比堆顶数字大的值，就替换掉堆顶，重新构建小顶堆，直到数据读取完。最后堆里就是要求的最大100个值。算法实现：

public static int[] topK(int[] array, int k) {    if (array == null || array.length == 0) {        return null;    }    int[] result = new int[k];    for (int i = 0; i < k; i++) {        result[i] = array[i];    }    if (array.length <= k) {        return result;    }    buildHeap(result);    for (int data : array) {        if (data > result[0]) {            result[0] = data;            heapify(result, 0, result.length);        }    }    return result;}private static void buildHeap(int[] arr) {    int length = arr.length;    for (int i = length / 2 - 1; i >= 0; i--) {        heapify(arr, i, length);    }}private static void heapify(int[] arr, int parentIndex, int length) {    int leftChild = parentIndex * 2 + 1;    int rightChild = parentIndex * 2 + 2;    int largest = parentIndex;    if (leftChild < length && arr[leftChild] > arr[parentIndex]) {        largest = leftChild;    }    if (rightChild < length && arr[rightChild] > arr[parentIndex]) {        largest = rightChild;    }    if (parentIndex != largest) {        int temp = arr[parentIndex];        arr[parentIndex] = arr[largest];        arr[largest] = temp;        heapify(arr, largest, length);    }}复制代码

建堆的时间复杂度是lgn，总共执行n此，所以时间复杂度是O(nlgn)。

2.利用冒泡排序的原理

为什么冒泡可以解决这种问题呢？有什么优缺点呢？首先冒泡编码相当简单，变量k*n次可以找到TopK。缺点自然就是要把所有数据都加载到内存进行遍历，而且时间复杂度高。算法实现：

public static int[] bubbleTopK(int[] arry, int k) {    //ToDo: 参数校验    for (int i = 0; i < k; i++) {        for (int j = arry.length - 1; j > i; j--) {            if (arry[j] > arry[j - 1]) {                int temp = arry[j];                arry[j] = arry[j - 1];                arry[j - 1] = temp;            }        }    }    return Arrays.copyOf(arry, k);}复制代码

3.利用快速排序的原理

用快排的思想来解Top K问题，必然要运用到”分治”。与快排相比，两者唯一的不同是在对”分治”结果的使用上。分治函数会返回一个position，在position左边的数都比第position个数小，在position右边的数都比第position大。我们不妨不断调用分治函数，直到它输出的position = K-1，此时position前面的K个数（0到K-1）就是要找的前K个数。

public static int[] quickTopK(int[] array, int k) {    //TODO: 参数校验    int index = partition(array, 0, array.length - 1);    int start = 0;    int end = array.length - 1;    while (index != k - 1) {        if (index < k - 1) {            start = index + 1;            index = partition(array, start, end);        } else if (index > k - 1) {            end = index - 1;            index = partition(array, start, end);        }    }    return Arrays.copyOf(array, k);}private static int partition(int[] array, int start, int end) {    if (array == null || start >= end) {        return 0;    }    int flag = array[start];    while (start < end) {        while (start < end && array[start] < flag) {            start++;        }        array[start] = array[end];        while (start < end && array[end] > flag) {            end--;        }        array[end] = array[start];    }    array[start] = flag;    return start;}复制代码