Top K问题

1、题目

给定一个长度为 N N N 的无序数组 a r r arr a rr，和一个正数 k ( k ≤ N ) k(k \le N)k (k ≤N )，返回前 k k k 个最大的数，即 Top k k k。

使用下列 3 个不同复杂度的三个方法实现：

1）O ( N ∗ l o g N ) O(N logN)O (N ∗l o g N )
2）O ( N + k ∗ l o g N ) O(N + klogN)O (N +k ∗l o g N )
3）O ( N + k ∗ l o g k ) O(N + k * logk)O (N +k ∗l o g k )

2、思路

对原数组进行从小到大排序，排好序后从右往左取出 k k k 个数即可。

public class MaxTopK {

    public static int[] maxTopK1(int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }
        int N = arr.length;
        k = Math.min(N, k);
        Arrays.sort(arr);
        int[] ans = new int[k];
        for (int i = N - 1, j = 0; j < k; i--, j++) {
            ans[j] = arr[i];
        }
        return ans;
    }
}

无序数组从下向上建大根堆的时间复杂度 O ( N ) O(N)O (N )，然后从堆中弹出 k k k 个数，而每次弹出堆顶后调整堆的时间复杂度为 O ( l o g N ) O(logN)O (l o g N )，所以弹出 k k k 个数的时间复杂度为 O ( k ∗ l o g N ) O(k*logN)O (k ∗l o g N )，因此总的时间复杂度为 O ( N + k ∗ l o g N ) O(N + k * logN)O (N +k ∗l o g N )。

public class MaxTopK {

    public static int[] maxTopK2(int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }
        int N = arr.length;
        k = Math.min(N, k);

        for (int i = N - 1; i >= 0; i--) {
            heapify(arr, i, N);
        }

        int heapSize = N;
        swap(arr, 0, --heapSize);
        int count = 1;
        while (heapSize > 0 && count < k) {
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
            count++;
        }
        int[] ans = new int[k];
        for (int i = N - 1, j = 0; j < k; i--, j++) {
            ans[j] = arr[i];
        }
        return ans;
    }

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

要求N N N个数中前 k k k 大的数，可以使用 改造快排或bfprt算法 先求出第 N − k N – k N −k 小的数 m m m（即第k k k大的数），时间复杂度 O ( N ) O(N)O (N )；

然后准备一个长度为 k k k 的数组，遍历一遍数组，只要数比 m m m 大就收集，假设收集到大于 m m m 的数有 x ( x < k ) x(x < k)x (x <k ) 个，那么剩下的 k − x k – x k −x 个毫无疑问都是 m m m，这个过程的时间复杂度为 O ( N ) O(N)O (N )；

最后，因为结果要求是有序的，所以对这个长度为 k k k 的数组进行排序，时间复杂度 O ( k ∗ l o g k ) O(k*logk)O (k ∗l o g k )。

因此，总的时间复杂度为 O ( N + k ∗ l o g k ) O(N + k *logk)O (N +k ∗l o g k )。

public class MaxTopK {

    public static int[] maxTopK3(int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }
        int N = arr.length;
        k = Math.min(N, k);

        int num = minKth(arr, N - k);
        int[] ans = new int[k];
        int index = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] > num) {
                ans[index++] = arr[i];
            }
        }
        for (; index < k; index++) {
            ans[index] = num;
        }

        Arrays.sort(ans);
        for (int L = 0, R = k - 1; L < R; L++, R--) {
            swap(ans, L, R);
        }
        return ans;
    }

    public static int minKth(int[] arr, int index) {
        int L = 0;
        int R = arr.length - 1;
        int pivot = 0;
        int[] range = null;
        while (L < R) {
            pivot = arr[L + (int) (Math.random() * (R - L + 1))];
            range = partition(arr, L, R, pivot);
            if (index < range[0]) {
                R = range[0] - 1;
            } else if (index > range[1]) {
                L = range[1] + 1;
            } else {
                return pivot;
            }
        }
        return arr[L];
    }

    public static int[] partition(int[] arr, int L, int R, int pivot) {
        int less = L - 1;
        int more = R + 1;
        int cur = L;
        while (cur < more) {
            if (arr[cur] < pivot) {
                swap(arr, ++less, cur++);
            } else if (arr[cur] > pivot) {
                swap(arr, cur, --more);
            } else {
                cur++;
            }
        }
        return new int[] { less + 1, more - 1 };
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

public class MaxTopK {

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {

            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean pass = true;
        System.out.println("测试开始，没有打印出错信息说明测试通过");
        for (int i = 0; i < testTime; i++) {
            int k = (int) (Math.random() * maxSize) + 1;
            int[] arr = generateRandomArray(maxSize, maxValue);

            int[] arr1 = copyArray(arr);
            int[] arr2 = copyArray(arr);
            int[] arr3 = copyArray(arr);

            int[] ans1 = maxTopK1(arr1, k);
            int[] ans2 = maxTopK2(arr2, k);
            int[] ans3 = maxTopK3(arr3, k);
            if (!isEqual(ans1, ans2) || !isEqual(ans1, ans3)) {
                pass = false;
                System.out.println("出错了！");
                printArray(ans1);
                printArray(ans2);
                printArray(ans3);
                break;
            }
        }
        System.out.println("测试结束了，测试了" + testTime + "组，是否所有测试用例都通过？" + (pass ? "是" : "否"));
    }

}

因为 k ≤ N k \le N k ≤N，所以方法三 O ( N + k ∗ l o g k ) O(N+k*logk)O (N +k ∗l o g k ) 最可能是最优解。

Original: https://blog.csdn.net/u011386173/article/details/128430093
Author: 明朗晨光
Title: Top K问题