By

Contents
  1. 1. 1. 一个无序的数组，快速找出第k小/大的数
    1. 1.1. LeetCode ：Kth Largest Element in an array
  2. 2. 2. 两个有序数组，找出第k小/大的数
  3. 3. 一一般情况
    1. 3.1. 一个类似的问题是 LeetCode： Median of Two Sorted Arrays
  4. 4. 3. 多个有序数组，找出第k小/大的数

几种问题：

  1. 一个无序的数组，快速找出第k小/大的数
  2. 两个有序数组，找出第k小/大的数

  3. 多个有序数组，找出第k小/大的数

  4. 合并两个有序数组

  5. 合并多个有序数组
  6. 合并两个链表
  7. 合并多个链表

1. 一个无序的数组，快速找出第k小/大的数

  • 解法1：排序（快排），然后再选择，时间O（n * log n)+O(k)=O（n * log n）

  • 解法2：选择或者交换排序。

    1. 遍历n个数，把最先遍历到的k个数存入到大小为k的数组中，假设它们即是最小的k个数；
    2. 对这k个数，利用选择或交换排序找到这k个元素中的最大值kmax（找最大值需要遍历这k个数，时间复杂度为O（k））；
    3. 继续遍历剩余n-k个数。假设每一次遍历到的新的元素的值为x，把x与kmax比较：如果x < kmax ，用x替换kmax，并回到第二步重新找出k个元素的数组中最大元素kmax‘；如果x >= kmax，则继续遍历不更新数组。

每次遍历，更新或不更新数组的所用的时间为O（k）或O（0）。故整趟下来，时间复杂度为 n*O（k）=O（n*k）。

  • 解法3：更好的办法是维护容量为k的最大堆，原理跟解法二的方法相似：

    1. 用容量为k的最大堆存储最先遍历到的k个数，同样假设它们即是最小的k个数；
    2. 堆中元素是有序的，令k1<k2<…<kmax（kmax设为最大堆中的最大元素）
    3. 遍历剩余n-k个数。假设每一次遍历到的新的元素的值为x，把x与堆顶元素kmax比较：如果x < kmax，用x替换kmax，然后更新堆（用时logk）；否则不更新堆。

这样下来，总的时间复杂度:O（k+（n-k）*logk）=O（n*logk）。此方法得益于堆中进行查找和更新的时间复杂度均为：O(logk)（若使用解法二：在数组中找出最大元素，时间复杂度：O（k））。

  • 解法4:一种在平均情况下，时间复杂度为O（N）的快速选择算法。如下述文字：

    • 选取S中一个元素作为枢纽元v，将集合S-{v}分割成S1和S2，就像快速排序那样
    • 如果k <= |S1|，那么第k个最小元素必然在S1中。在这种情况下，返回QuickSelect(S1, k)。
    • 如果k = 1 + |S1|，那么枢纽元素就是第k个最小元素，即找到，直接返回它。
    • 否则，这第k个最小元素就在S2中，即S2中的第（k - |S1| - 1）个最小元素，我们递归调用并返回QuickSelect(S2, k - |S1| - 1)。

此算法的平均运行时间为O(n)。

LeetCode ：Kth Largest Element in an array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static int partition(int[] nums, int low, int high){
	int pivot = nums[low];
	while(low<high){
		while(low<high && nums[high]>=pivot) high--;
		nums[low]=nums[high];
		while(low<high && nums[low]<=pivot) low++;
		nums[high] =nums[low];
	}
	nums[low]=pivot;
	return low;
}
public static int findKthLargest(int[] nums, int k) {
	k = nums.length-k;
	int low = 0;
	int high = nums.length-1;
	while(low < high){
    	int pivotloc = partition(nums,low,high);
    	if(pivotloc==k) 
    		break;
    	else if(k<pivotloc){
    		high = pivotloc-1;
    	}else if(k>pivotloc){
    		low = pivotloc+1;
    	}
	}
	return nums[k];
}

2. 两个有序数组，找出第k小/大的数

来源

一一般情况

采用一种类似于二分查找的方法。
基于中位数的比较。为什么使用中位数而不是在两个数组中各取k/2大的数呢，是因为只要数组的长度不为0，那么中位数总是存在的，而第K/2的数就不一定了，数组的长度很有可能小于k/2哦。通过这样的方法我们可以规避一大票边界问题。

我们将两个数组按照3种情况来讨论：

1、两个数组的长度均为奇数。
我们设a数组的中位数下标为x，b数组的中位数下标为y，则如下图所示，a数组的长度为2x+1，b数组的长度为2y+1，总的元素的个数为2x+2y+2。

我们现在需要探讨的就是k是大于x+y+1，还是小于x+y+1的情况，也就是我们想找的第k大的数是在a、b数组归并后的数组中的前一半内，还是在后一半内。不失一般性，我们讨论当a[x] <= b[y]的情况，

当k <= x + y + 1，也即k属于归并数组的前一半时，从下图可以看出黄色区域明显不包含第k个数。原因很简单，因为b[y]大于等于蓝色部分的数，而蓝色部分的数目即为x+y+1，恰好为全体数的前一半的个数，也就是说黄色区域的数不可能属于归并后的前一半数组，可以排除在外，在剩余的两个数组中寻找第k大数。

当k > x + y + 1，也即k属于归并后数组的后一半，那么从下图可以看出黄色区域明显不包含第k个数。原因是黄色区域的数必然小于蓝色区域的数，而蓝色区域的数的数目之和即为x+y+1，恰好为归并后数组的和的一半，因此可以将黄色区域排除在外，注意在剩余的两个 数组中寻找第 k - x -1 大数。

当a[x] > b[y]时，只是上述的情况反一下，读者可以自己试着推一下。

2、两个数组的长度均为偶数
我们寻找a数组的上中位下标，记为x，b数组的下中位下标，记为y，如下图所示。这样错开中位数的目的是为了在将来做排除时能够保证像奇数情况下能将第k大数归类到前一半或者后一半的完美性质。

这样看来，a数组长度为2x + 2，b数组长度为2y，因此归并后的数组长度为2x + 2y + 2，与奇数情况一致。
不失一般性，我们讨论a[x] <= b[y]的情况。

当k <= x + y + 1，也即k属于归并数组的前一半时，如下图所示。显然黄色部分可以排除在外，因为黄色部分一定大于等于蓝色部分，而蓝色部分的长度之和为x+y+1，恰好为归并数组的一半。也就是说黄色部分必然位于归并数组的后一半，不可能包含第k个数。之后我们在排除了黄色区域的两个数组中寻找第k个数。

当k > x + y + 1，也即k属于归并数组的后一半时，如下图所示。显然黄色部分可以排除在外，因为黄色部分一定小于蓝色部分，而蓝色部分的长度之和为x+y+1，恰好为归并数组的一半。也就是说黄色部分必然位于归并数组的前一半，不可能包含第k个数。之后我们在排除了黄色区域的两个数组中寻找第k - x - 1个数。

当a[x] > b[y]时，只是上述的情况反一下，读者可以自己试着推一下。

3、当a、b数组的长度为一奇一偶的情况。
若 k = 1，那么直接返回min(a[0], b[0])即可。
若 k > 1，不妨假设 a[0] < b[0]，那么a[0]必然是两个数组中最小的数，那么排除a[0]后我们可以在a、b两个数组中寻找第k-1个数，并且a的长度减一，这样就将原问题转化为上述1、2讨论的问题。

4、当a、b数组的长度有一个为0时，直接返回另一个长度非0数组的第k个数即可。

综上所述，我们在每次递归的时候都去除了一个数组中包含一个中位数的一半元素，直到一个数组被完全排除在外为止，直接去另一个数组的第k个数。上面的过程中由于每次总会去除一个中位数，因此算法总能够收敛，不难证明算法的时间复杂度为O(logN)。

一个类似的问题是 LeetCode： Median of Two Sorted Arrays

3. 多个有序数组，找出第k小/大的数

Contents
  1. 1. 1. 一个无序的数组，快速找出第k小/大的数
    1. 1.1. LeetCode ：Kth Largest Element in an array
  2. 2. 2. 两个有序数组，找出第k小/大的数
  3. 3. 一一般情况
    1. 3.1. 一个类似的问题是 LeetCode： Median of Two Sorted Arrays
  4. 4. 3. 多个有序数组，找出第k小/大的数