面试题之TopN

在面试中经常遇到需要在海量数据中找到最大的前N元素，下面主要对这个问题进行讲解。
常见的几种方法有冒泡排序，堆排序以及基于快速排序的减治法。

解法一：冒泡排序

假如总共有M个元素，要找到前N个元素，使用冒泡排序总共需要进行N趟排序，每趟排序都可以找到最大的元素。
使用Java实现代码如下。

public class BubbleSort {
    public static void solution(int[] nums, int k){
        for (int j = 0; j < k; j++) {
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] > nums[i +1]){
                    swap(nums, i, i+1);
                }
            }
        }
    }

    private static void swap(int[] nums, int i, int i1) {
        int temp = nums[i];
        nums[i] = nums[i1];
        nums[i1] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 6, 12, 9, 10, 2};
        int k = 3;
        solution(nums, k);
        for (int i = 0, index = nums.length - 1; i < k; i++, index--) {
            System.out.println(nums[index]);
        }
    }
}

上面的程序输出结果是：

12
10
9

这个算法的时间复杂度是O(N*K)
###解法二：堆排序
堆排序首先建立堆，然后对堆进行调整，通过不断的调整得到最大或者最小的元素。这里有个小技巧：最大的k个元素使用小顶堆，最小的k个元素使用大顶堆。
思路：当我们需要找最大的k个元素时，先创建一个小顶堆，由于堆顶是最小的元素，所以把剩下的N-k个元素一起和堆顶元素作比较，如果比堆顶元素大，就和堆顶元素进行置换，然后调整。直到N-k个元素调整完毕，那么堆里面的元素就是最大的k个元素。

public class HeadSort {
    public static void main(String[] args) {
        int[] nums = {3, 1, 6, 12, 9, 10, 2};
        int[] res = topK(nums, 4);
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i] + ", ");
        }
    }

    public static void heapify(int[] array, int index, int length) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        int min = index;
        // 建立
        if (left < length && array[left] < array[min]) {
            min = left;
        }
        if (right < length && array[right] < array[min]) {
            min = right;
        }
        if (index != min) {
            swap(array, min, index);
            // 继续向下调整
            heapify(array, min, length);
        }
    }

    public static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    public static void buildHeap(int[] array) {
        int length = array.length;
        for (int i = length / 2 - 1; i >= 0; i--) {
            heapify(array, i, length);
        }
    }

    public static void setTop(int[] array, int top) {
        array[0] = top;
        heapify(array, 0, array.length);
    }

    public static int[] topK(int[] array, int k) {
        int[] top = new int[k];
        for (int i = 0; i < k; i++) {
            top[i] = array[i];
        }
        buildHeap(top);
        System.out.println(top[0]);
        for (int j = k; j < array.length; j++) {
            int temp = top[0];
            if (array[j] > temp) {
                setTop(top, array[j]);
            }
        }
        return top;
    }
}

这个算法只需要的时间复杂度是O(Nlogk)

解法三：基于减治法的快速排序

减治法和分治法都是经典的算法思想，但是分治法是将一个问题分成多个小问题进行求解，减治法是将一个大问题转化为一个小问题进行求解。
下面的代码就采用的是减治法的思想。

public class QuickSort {
    public static void quickSort(int[] a , int low, int high){
        if (low >= high){
            return;
        }
        int index = partition(a, low, high);
        // 前闭后闭区间
        quickSort(a, index + 1, high);
        quickSort(a, low , index);
    }

    private static int partition(int[] a, int low, int high) {
        int i = low;
        int j = high + 1;
        int shaoBing = a[i];

        while(true){
            while(a[++i] < shaoBing){
                if (i == high) break;
            }
            while(a[--j] > shaoBing){
                if (j == low) break;
            }
            if(i >= j) break;
            swap(a, i, j);
        }
        swap(a, low, j);
        return j;
    }

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

    public static void topK(int[] array, int k) {
        if (array != null && array.length > 0) {
            int low = 0;
            int high = array.length - 1;
            int index = partition(array, low, high);
            while (index != k - 1) {
                if (index > k - 1) {
                    high = index - 1;
                    index = partition(array, low, high);
                }
                if (index < k - 1) {
                    low = index + 1;
                    index = partition(array, low, high);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 6, 12, 9, 10, 2};
        topK(nums, 4);
        for (int i = 0; i < 4; i++) {
            System.out.print(nums[i] + ", ");
        }
    }
}

这个算法的时间复杂度是O(N)