两个已排序的数组求中间值(寻找k小值算法)

2016-12-21 | 分类 blog | 标签 javascript 算法寻找k小值 leetcode | 浏览

寻找k小值

起由

这是leetcode上的一道经典题目，最近正好准备重新补下基础，于是研究了下这个算法。

需求描述

有序数组(升序)，X(M个数)和Y(N个数)，数组合并后为Z(L个数)，求两个数组合并后的Z数组的中间值，比如

[1,2,3,4] 
的中间值是(2+3)/2=2.5
[1,2,3] 
的中间值是2

算法步骤

前提分析

数组求中位数有两种情况(以下第×位数从1开始算起)

若合并后L为偶数，那么中间数为第L/2位数和第(L/2+1)位数的平均值 其中L/2后取整
若合并后为奇数，那么中间数为 第(L/2+1)位数

所以，以上找中间数问题就转变成了在两个已排序数组中找第k大的数(第k小值)

解决思路(假设是理想状态下)

每次分别在X数组中和Y数组中取k/2个值进行比较(加起来正好k个)，下述为了方便，将k/2-1用middle表示
比较X[middle]和Y[middle]
- 如果X[middle]<Y[middle]，意味着第k位数>=Y[middle]>X[middle]，所以X[middle]和之前的数肯定不会数第k位数，那么我们可以抛弃X数组中middle以及前面部分，
```
  X=X.slice(middle),Y=Y,k=k-middle;
```
  重新进行第一步比较
- 如果X[middle]>Y[middle]，意味着第k位数>=X[middle]>Y[middle]，那么我们可以抛弃Y数组中middle以及前面部分，
```
  X=X,Y=Y.slice(middle),k=k-middle;
```
  重新进行第一步比较
- 如果X[middle]==Y[middle]，意味着X和Y中正在比较的k位数全部<=第k个数。所以第k个数就在正在比较的数之中，而因为数组是升序，所以不是X[middle]，就是Y[middle] 我们只需要取最终的值为X[middle]即可

实现步骤(以下数组是从0开始算起的)，考虑到一些可能的实际情况，找数组中第K大的数

第一步，我们交换两个数组的位置，确保X大小小于等于Y(如果X已经大于Y，则交换两个数组)
第二步，如果X数组为0，那么第k位数肯定在Y中，并且值就是Y[k-1]
第三步，如果k为1，那么只需要取Math.min(X[0],Y[0])，因为第一位数只可能是两个数组中的首位中的最小的一个

第四步，如果k不满足以上特殊值，则分别比较X数组和Y数组中特定的值

  var partA = ~~Math.min(k/2,m),partB = k - partA;
  //这时候X中需要比较的值的分布可能为下述情况(当k/2为1时，则只有一个partA)
  0,...,partA-1
  //Y中需要比较的值得分布可能为
  0,...,partB-1
  //而且X中需要比较的数和Y中需要比较的数加起来刚好有k位，而且(第k位数>=X[partA-1],第k位数>=X[partB-1])

如果X[partA-1]<Y[partB-1]，(原理上述已经分析)
```
  X=X.slice(partA),Y=Y,k=k-partA;
```
重新进行第一步比较
如果X[partA-1]>Y[partB-1]，(原理上述已经分析)
```
  X=X,Y=Y.slice(partB),k=k-partB;
```
重新进行第一步比较
如果X[partA-1]==Y[partB-1]，(原理上述已经分析) 取最终的值为X[partA-1]

算法复杂度

空间复杂度

O(1)

这个算法没有额外的空间要求

时间复杂度

这个算法每次分别去掉某一个数组中的某一部分，假设X数组长度为，Y数组长度为N。那么复杂度计算方式为:

0(lgM+lg(N))=O(lgMN)<=O(2lg(M+N)) = O(lg(M+N))

算法实例

以下按照上述算法实现步骤，基于一个实例进行分析。

前提

X=[1,3,5];
Y=[1,2,3,4];

求X和Y的中间值

准备工作

可知，初始化时X中有3位，Y中有4为，所以一共7位，为奇数。那么我们所求是第4=(3+4)/2+1位数

实现过程

第一步，X长度小于Y，不需要交换，其中X数组的长度m为3，Y数组的长度n为4，k为4

第二步，取特殊值进行比较

  var partA = ~~Math.min(k/2,m);//2
  var partB = k - partA; //2

第三步，比较X[partA-1]和Y[partB-1]，结果是X[1]>Y[1]，所以舍弃Y中部分值，重新进行比较
```
  X=X,Y=Y.slice(partB),k=k-partB;
```
舍弃完毕后，X为1,3,5，Y为3,4，k为2 之后交换X和为，X换为3,4，m为2，Y换位1,3,5，n为3

第四步，重新去特殊值进行比较

  var partA = ~~Math.min(k/2,m);//1
  var partB = k - partA; //1

第五步，比较X[partA-1]和Y[partB-1]，结果是X[0]>Y[0]，所以舍弃Y中部分值，重新进行比较
```
  X=X,Y=Y.slice(partB),k=k-partB;
```
舍弃完毕后，X为3,4，Y为3,5，k为1 不需要交换x与Y，此时m为2，n为2
第六步，重新比较新的数组，由于符合条件k==1，所以
```
  第k个值 = Math.min(X[0],Y[0]); //3
```
至此，整个算法流程运行完毕，最终的中间值为3

图示

实现代码示例

以下是相应算法的代码实现

JS代码实现

function findMedianSortedArrays2(nums1,nums2) {
		var m = nums1.length,n = nums2.length;
		var total = m+n;
		
		//找到两个排序数组中的第k个小数，内部假设m小于n
		var findKth = function(X,Y,m,n,k){
			if(m>n){
				//颠倒mn的顺序
				return findKth(Y,X,n,m,k);
			} else if(m===0){
				//如果X数组为空，那么K肯定就在Y数组中
				return Y[k-1];
			} else if(k===1){
				//只有一位，由于是升序，所以必然是X[0]或Y[0]
				return Math.min(X[0],Y[0]);
			}
			
			//divide k into two parts,最小为1
			//可以肯定得是partA和partB都<=K
			var partA = ~~Math.min(k/2,m),partB = k - partA;
			//第一位数其实是X[0]，因为程序从0开始
			//以下判断时关键，每一次都可以去掉不符合要求的一部分，进行精简
			if(X[partA-1] < Y[partB-1]){
				return findKth(X.slice(partA),Y,m-partA,n,k-partA);
			} else if(X[partA-1] > Y[partB-1]) {
				return findKth(X,Y.slice(partB),m,n-partB,k-partB);
			} else {
				//如果X数组中的第partA位和Y数组中的第partB为相等
				//由于X中有1,...,partA
				//Y中有1,...,partB
				//两者加起来刚好为k,而不管k在X中还是Y中，都必须满足X[k]>=X[partA]=X[partB]
				//所以k只可能是partA或partB(原因是X和Y中加起来已经有K个数小于等于X[k]了，所以K只能在这里面)
				return X[partA-1];
			}
		};
		
		if(total%2!==0){
			 return findKth(nums1, nums2, m,n, ~~(total / 2)+1);  
		} else {
			return (findKth(nums1, nums2, m,n, ~~(total / 2)+1 )+findKth(nums1, nums2, m,n, ~~(total / 2 )))/2;  
		}
	};