KK's blog

每天积累多一些

0%

LeetCode 004 Median of Two Sorted Arrays

Posted on Edited on Disqus:

LeetCode 004 Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1: 

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2: 

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题目大意：

求两个有序数组中的中位数。

数值二分法解题思路(推荐)：

由于是求中位数或第k小的数，根据题型分类用Heap或binary select。Heap的话，由于是有序，所以优势不大，复杂度为O[(m+n)log2].
考虑用binary select，思路比较直接，就是将两个数组看成一个，统计个数的时候由于有序，分别在两数组用二分法统计。

注意事项：

  1. 中位数有1-2两个。用单一元素数组的例子来确定+1还是-1，Line 6
  2. 统计最大最小值，注意空数组
  3. 统计count用bisect不需要+1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
	m, n = len(nums1), len(nums2)
	if (m + n) % 2 == 1:
		return self.find_kth_smallest(nums1, nums2, (m + n) // 2)
	else:
		return (self.find_kth_smallest(nums1, nums2, (m + n) // 2) + self.find_kth_smallest(nums1, nums2, (m + n) // 2 - 1)) / 2

def find_kth_smallest(self, nums1, nums2, k):
	min_val, min_val2 = nums1[0] if nums1 else float('inf'), nums2[0] if nums2 else float('inf')
	max_val, max_val2 = nums1[-1] if nums1 else float('-inf'), nums2[-1] if nums2 else float('-inf')
	start, end, epsilon = min(min_val, min_val2), max(max_val, max_val2), 0.5
	while end - start > epsilon:
		mid = start + (end - start) / 2
		count = self.count(nums1, nums2, mid)
		if k < count:
			end = mid
		elif k > count:
			start = mid
		else:
			start = mid
	return math.floor(end)

def count(self, nums1, nums2, mid):
	return bisect.bisect(nums1, mid) + bisect.bisect(nums2, mid)  # remember

算法分析：

时间复杂度为O(nlog(|hi-lo|/delta))，由于数据大小范围是10^6, 而前面的n是基于全数组扫描，这里用二分法，n变成log(m)+log(n)
时间复杂度为O(logm + logn)，空间复杂度O(1)

Merge sort算法II解题思路：

既然是有序，考虑用merge sort中的merge步骤
merge sort里面的数组是无序，但这里是有序，所以merge这个步骤可以改进，不是一个个数比较，可以分别取第k/2进行比较，原理是一样的，但效率更高。
若num1[k/2] < num2[k/2]相当于nums1[i] <= nums2[j]，此时表示num1[0..k/2]都满足小于等于第k个数的结果数组中。i移位，不是移一位，而是移k/4.
这样得到方法三。方法三解释比较难懂，用mergesort模拟较易懂。
一般是对数组二分，此法采用对k二分

注意事项：

  1. 若i或j用完，返回另一个数组的元素，下标是j+k或i+k，k此时是剩余的k

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def findMedianSortedArrays2(self, nums1: List[int], nums2: List[int]) -> float:
	m, n = len(nums1), len(nums2)
	if (m + n) % 2 == 1:
		return self.find_kth_smallest2(nums1, nums2, (m + n) // 2)
	else:
		return (self.find_kth_smallest2(nums1, nums2, (m + n) // 2) + self.find_kth_smallest2(nums1, nums2, (m + n) // 2 - 1)) / 2

def find_kth_smallest2(self, nums1, nums2, k):
	i, j = 0, 0
	while i < len(nums1) and j < len(nums2) and k > 0:
		if nums1[i] <= nums2[j]:
			i += 1
		else:
			j += 1
		k -= 1
	if i == len(nums1):  # remember dont use (not nums1)
		return nums2[j + k]  # remember use j+k rather than k
	if j == len(nums2):
		return nums1[i + k]
	return min(nums1[i], nums2[j])

算法分析：

时间复杂度为O(m + n)，空间复杂度O(1)。

二分法算法III解题思路：

将上面的方法换成递归，if判断语句换成递归终止条件，+1变成+k/2，注意判断越界
说起来轻松，但非常容易错，不推荐

注意事项：

  1. 中位数有1-2两个。
  2. off by 1的问题。递归子函数要用(k+1)//2而不是k//2因为若k=1时候，k//2就不能移动一位。
  3. 若nums中i + k // 2越界，不碰nums，右移j，因为nums不能右移那么多, 所以num1赋最大值不是最小值
  4. 终止条件i >= len(nums1)取大于号，跟上面不同，因为可能越界

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def findMedianSortedArrays3(self, nums1: List[int], nums2: List[int]) -> float:
	m, n = len(nums1), len(nums2)
	if (m + n) % 2 == 1:
		return self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2)
	else:
		aa = self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2)
		bb = self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2 - 1)
		return (self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2)
				+ self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2 - 1)) / 2

    def find_kth_smallest3(self, nums1, nums2, i, j, k):
        if i >= len(nums1):  # remember to use >= rather than ==
            return nums2[j + k]
        if j == len(nums2):
            return nums1[i + k]
        if k == 0:
            return min(nums1[i], nums2[j])
        num1 = nums1[i + k // 2] if i + k // 2 < len(nums1) else float('inf')  # remember sys.maxsize not minus
        num2 = nums2[j + k // 2] if j + k // 2 < len(nums2) else float('inf')
        if num1 <= num2:  # remember the steps are same by moving i and k, k + 1
            return self.find_kth_smallest3(nums1, nums2, i + (k + 1) // 2, j, k - (k + 1) // 2)
        else:
            return self.find_kth_smallest3(nums1, nums2, i, j + (k + 1) // 2, k - (k + 1) // 2)

Java实现

题目要求log(m+n)复杂度，也就提示要对数组总长做二分法。因为要同时处理两个数组所以考虑用递归版二分法。因奇偶中位数有1-2个，
所以加强命题为求两有序数组的第k个数(k>=1)。
对k的值进行二分k/2，先尝试num1数组的第k/2个数和num2数组的第k/2个数。若它们相等，表示它们即为第k个数。也就是比如求第4个数，
分别在两数组中取前两个，平均分配名额。此题类似于求前k大的数(算法文档4.1.13)用统计个数的方法来判断走左还是右。若它们不等，不妨假设
aKey<bKey，这样表示第k个数一定不会是aKey，因为即使比bKey小的数均小于aKey的话（有k/2-1个），总共有k/2-1+k/2-1=k-2个数小于
aKey，也就是aKey为第k-1个数，不可能为第k个数，它只可能出现是bKey或者在num1中比aKey大的数。既然aKey不是解，比aKey小的数
更不可能是解。所以，可以抛掉num1[0, k/2]这部分，转而求num1[k/2+1,nums.length-1]以及nums2的第k-k/2个数，抛掉部分会影响结果
吗？答案是否定的。比如
1 2 3 4
0 6 7 8
k=4，比较2和6,2<6抛掉1 2，转求[3,4],[0,6,7,8]的第2个数，答案仍为3，不影响结果，因为前k/2个数即使有些在nums2也不会影响
最后结果，求的是第k个。
1 2 3 4
0 6 7 8
第k=4数可能出现在num1[k/2+1,nums.length-1]=3或num2=6（下面例子），所以保留部分是正确的。
主要思路是每次递归抛掉k/2个数，数组规模减少k/2，k变成k-k/2, API为left, left2表示新数组的左边界(因为永远抛左边部分)以及k。
递归终止条件为

  1. left越界，这时此数组的数刚好用完或此数组为空(不会越界太多，否则aKey无穷大会递归到num2)。归结为求另一数组[left..]的第k个数.
  2. k为1时候，是基本情况，表示求两数组的第1个数，只要返回左端的最小值即可。

注意事项：

  1. 中位数有1-2两个。
  2. off by 1的问题。若API中的k定义为第k个数k>=1，若总长len=5，中位数为第len/2+1=3个数。所以在递归函数中，数组下标用到k时
    都要-1。抛掉[left, left+k/2-1],递归[left+k/2..]。
  3. 若nums中left+k/2-1越界，不碰nums，右移left2，因为nums不能右移那么多。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public double findMedianSortedArrays(int[] num1, int[] num2){
	int len = num1.length+num2.length;
	if(len%2==1)
		return findKth(num1,num2,0,0,len/2+1);
	else return (findKth(num1,num2,0,0,len/2)+findKth(num1,num2,0,0,len/2+1))/2.0;
}

public int findKth(int[] num1, int[] num2, int left, int left2, int k){
	if(left>=num1.length)
		return num2[left2+k-1];
	if(left2>=num2.length)
		return num1[left+k-1];
	if(k==1)
		return Math.min(num1[left], num2[left2]);;
	
	int aKey = left+k/2-1<num1.length?num1[left+k/2-1]:Integer.MAX_VALUE;
	int bKey = left2+k/2-1<num2.length?num2[left2+k/2-1]:Integer.MAX_VALUE;
	if(aKey<bKey)
		return findKth(num1,num2,left+k/2,left2,k-k/2);
	else
		return findKth(num1,num2,left,left2+k/2, k-k/2);
}

算法分析：

假设两数组总长度为N，k为中位数即N/2，每次抛掉k/2也就是子问题规模为N-k/2=N-N/4=3N/4. f(N)=f(3N/4)+1.
利用master理论b=4/3, a=1, f(n)=1代入时间复杂度为O(log(m+n))，空间复杂度O(1)。

Free mock interview