问题描述
无序数组求第K大的数,其中K从1开始算。
例如:[0,3,1,8,5,2]这个数组,第2大的数是5
OJ可参考:LeetCode_0215_KthLargestElementInAnArray
堆解法
设置一个小根堆,先把前K个数放入小根堆,对于这前K个数来说,堆顶元素一定是第K大的数,接下来的元素继续入堆,但是每入一个就弹出一个,最后,堆顶元素就是整个数组的第K大元素。代码如下:
public static int findKthLargest3(int[] nums, int k) { PriorityQueue<Integer> h = new PriorityQueue<>(); int i = 0; // 经历这个循环,前K个数的第K大的数就是h的堆顶元素 while (i < k) { h.offer(nums[i++]); } // 每次入一个,出一个,这样就保证了堆顶元素永远保持第K大的元素 while (i < nums.length) { h.offer(nums[i++]); h.poll(); } return h.peek(); }
由于每次堆需要logK的调整代价, 所以这个解法的时间复杂度为O(N*logK)
改进快排算法
快速排序中,有一个partition的过程, 代码如下,注:以下代码是从大到小排序的partition过程
private static int[] partition(int[] nums, int l, int r, int pivot) { int i = l; int more = l - 1;//大于区域 int less = r + 1; // 小于区域 while (i < less) { if (nums[i] > pivot) { swap(nums, i++, ++more); } else if (nums[i] < pivot) { swap(nums, i, --less); } else { i++; } } return new int[]{more + 1, less - 1}; }
这个过程主要的作用是将nums数组的l...r区间内的数,将:
- 小于pivot的数放右边
- 大于pivot的数放左边
- 等于pivot的数放中间
返回两个值,一个是左边界和一个右边界,位于左边界和右边界的值均等于pivot,小于左边界的位置的值都大于pivot,大于右边界的位置的值均小于pivot。简言之:如果要排序,pivot这个值在一次partition以后,所在的位置就是最终排序后pivot应该在的位置。
所以,如果数组中某个数在经历上述partion之后正好位于K-1位置,那么这个数就是整个数组第K大的数。
完整代码如下:
public class LeetCode_0215_KthLargestElementInAnArray { // 快排改进算法 // 第K小 == 第 nums.length - k + 1 大 public static int findKthLargest2(int[] nums, int k) { return p(nums, 0, nums.length - 1, k - 1); } // nums在L...R范围上,如果要排序(从大到小)的话,请返回index位置的值 public static int p(int[] nums, int L, int R, int index) { if (L == R) { return nums[L]; } int pivot = nums[L + (int) (Math.random() * (R - L + 1))]; int[] range = partition(nums, L, R, pivot); if (index >= range[0] && index <= range[1]) { return pivot; } else if (index < range[0]) { return p(nums, L, range[0] - 1, index); } else { return p(nums, range[1] + 1, R, index); } } private static int[] partition(int[] nums, int l, int r, int pivot) { int i = l; int more = l - 1;//大于区域 int less = r + 1; // 小于区域 while (i < less) { if (nums[i] > pivot) { swap(nums, i++, ++more); } else if (nums[i] < pivot) { swap(nums, i, --less); } else { i++; } } return new int[]{more + 1, less - 1}; } public static void swap(int[] nums, int t, int m) { int tmp = nums[m]; nums[m] = nums[t]; nums[t] = tmp; }}
其中p方法表示:nums在L...R范围上,如果要排序(从大到小)的话,请返回index位置的值。
int pivot = nums[L + (int) (Math.random() * (R - L + 1))];
这一行表示随机取一个值pivot出来,用这个值做后续的partition操作,如果index恰好在pivot这个值做partition的左右边界范围内,则pivot就是排序后第index+1大的数(从1开始算)。
bfprt算法
brfpt算法和改进快排算法主流程上基本一致,只是在选择pivot的时候有差别,快排改进是随机取一个数作为pivot, 而bfprt算法是根据一定的规则取pivot,伪代码表示为:
public class LeetCode_0215_KthLargestElementInAnArray { public static int findKthLargest2(int[] nums, int k) { return bfprt(nums, 0, nums.length - 1, k - 1); } // nums在L...R范围上,如果要排序(从大到小)的话,请返回index位置的值 public static int bfprt(int[] nums, int L, int R, int index) { if (L == R) { return nums[L]; } //int pivot = nums[L + (int) (Math.random() * (R - L + 1))]; int pivot = medianOfMedians(nums, L, R); int[] range = partition(nums, L, R, pivot); if (index >= range[0] && index <= range[1]) { return pivot; } else if (index < range[0]) { return bfprt(nums, L, range[0] - 1, index); } else { return bfprt(nums, range[1] + 1, R, index); } } ....}
其中
int pivot = medianOfMedians(nums, L, R);
就是bfprt算法最关键的步骤,mediaOfMedians这个函数表示:
将num分成每五个元素一组,不足一组的补齐一组,并对每组进行排序(由于固定是5个数一组进行排序,所以排序的时间复杂度O(1)),取出每组的中位数,组成一个新的数组, 对新的数组求其中位数,这个中位数就是我们需要的值pivot。
public static int medianOfMedians(int[] arr, int L, int R) { int size = R - L + 1; int offSize = size % 5 == 0 ? 0 : 1; int[] mArr = new int[size / 5 + offSize]; for (int i = 0; i < mArr.length; i++) { // 每一组的第一个位置 int teamFirst = L + i * 5; int median = getMedian(arr, teamFirst, Math.min(R, teamFirst + 4)); mArr[i] = median; } return bfprt(mArr, 0, mArr.length - 1, (mArr.length - 1) / 2); } public static int getMedian(int[] arr, int L, int R) { Arrays.sort(arr, L, R); return arr[(R + L) / 2]; }
注:mediaOfMedians方法中最后一句:
return bfprt(mArr, 0, mArr.length - 1, (mArr.length - 1) / 2);
就是利用bfprt算法拿整个元素中间位置的值。
关于bfprt算法的两个问题
- 为什么是5个一组
- 为什么严格收敛到O(N)
请参考:
三种解法复杂度分析
算法 | 时间 | 空间 |
---|---|---|
堆 | O(N*logK) | O(N) |
快排改进 | 概率上收敛到:O(N) | O(1) |
bfprt | 严格收敛到:O(N) | O(N) |
相关题目
LeetCode_0004_MedianOfTwoSortedArrays
第K小的数值对
长度为N的数组arr,一定可以组成N^2个数值对。例如arr = [3,1,2],数值对有(3,3) (3,1) (3,2) (1,3) (1,1) (1,2) (2,3) (2,1) (2,2),也就是任意两个数都有数值对,而且自己和自己也算数值对。数值对怎么排序?规定,第一维数据从小到大,第一维数据一样的,第二维数组也从小到大。所以上面的数值对排序的结果为:(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3), 给定一个数组arr,和整数k,返回第k小的数值对。