LeetCode刷题MEDIM篇线性时间查找整型数组中最大的k个数

LeetCode刷题MEDIM篇线性时间查找整型数组中最大的k个数

题目

一个整数数组，n个元素，寻找最大的m个数，时间复杂度为O（n）

分析

以前美团面试问过，后来也没有研究一下，现在学习一下解题思路。

最大的n个，显然其他的不关系，n个元素之间的关系也不关心，考虑用快速排序，因为快速排序一遍之后，privotkey对应的元素就是第privotkey大的元素。对了，这里说的第几大貌似不是正确的意思，是从小开始数的第几大，没有关系，为了代码方便实现，我们暂时这样理解。

除了快速排序的代码，需要注意点：

• 第几大的处理，用总数-代码中的结果+1就可以，这个简单
• 第一次快速排序后，判断privotLoc对应的元素位置加1，是否大于k，如果大于，证明第k大元素在其右侧，反之在左侧。
• 输出结果并非完全排序的，因为找到第几大的元素后，就会终止排序。这样才能提高算法效率
• 相等的情况，意味着我们找到第k大元素，注意相等指的是privotLoc+1=k

package com.puhui.flowplatform.manage;public class TestQuickSort {public static Integer quickSort(int[] r, int k, int low, int high) {int privotLoc = partition(r, k, low, high);int temp = privotLoc+1;if (k<temp) {return quickSort(r, k, low, privotLoc - 1);} else if (k>temp) {//注意右侧部分不是k，是k-privotLoc，因为在右侧递归，长度减去了一部分return quickSort(r, k, privotLoc + 1, high);} else {System.out.println("找到了第" + k + "大的数,不再排序，所求为:" + r[privotLoc]);return r[privotLoc];}}static int partition(int a[], int k, int low, int high) {int privotKey = a[low];while (low < high) {while (low < high && a[high] >= privotKey) {--high;};swap(a, low, high);while (low < high && a[low] <= privotKey) {++low;}swap(a, low, high);}return low;}private static void swap(int[] number, int i, int j) {int t;t = number[i];number[i] = number[j];number[j] = t;}public static void display(int[] R) {System.out.println();for (int i = 0; i < R.length; i++) {System.out.print(R[i] + " ");}}public static void main(String[] args) {int[] R = {71, 88, 93, 77, 5, 16, 63, 74, 89, 18};//这里的k是从小开始数的第几大，所以相比正确的理解，需要总数减去k//比如最大的4个数  10-4+1=7int k = 7;display(R);quickSort(R, k , 0, R.length - 1);display(R);}}

解法二

在数组元素值不是太大的情况下，可以考虑利用计数排序，利用空间换时间，具体算法参考我的另一个文章：