leetcode Median of Two Sorted Arrays

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)).
You may assume nums1 and nums2 cannot be both empty.
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

  分析:
  这个题本质是一个查找问题,并且两个数组已经有顺序,可以采用折半查找。但是由于是两个数组,因此需要在两个数组之间进行混合折半查找。如果m+n为奇数,中位数为最中间的那一个数;如果m+n为偶数,中位数为中间两个数的平均值。那么,如果在两个数组中进行如上的查找呢?可以发现,不论m+n是偶数还是奇数,取第k=(m+n+1)/2个与第k=(m+n+2)/2个的平均值总能找到中位数。

1、在保证时间复杂度的同时,尽量节约空间复杂度,因此,这里不将代码进行拷贝。

2、利用两个指针i和j来指示两个数组的起始位置,如果两个i或者j已经大于了对应数组的长度,则寻求的中位数一定在另一个数组。

3、查找k时,判断每个数组里面是否有k/2个元素,如果有就将其取出;如果没有,就将median设置为最大整数(因为每次迭代需要淘汰k/2个元素,如果某个数组没有这么多元素,自然无法从该数组中淘汰元素,只能从另一个数组中淘汰元素,因此设置最大整数,保证其不会被淘汰)。
  C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2 = nums2.size();
int leftk = (len1 + len2 + 1)/2;
int rightk = (len1 + len2 + 2)/2;
return (findK(nums1, 0, len1, nums2, 0, len2, leftk)
+ findK(nums1, 0, len1, nums2, 0, len2, rightk))/2.0;
}

int findK(vector<int>& nums1, int i, int len1, vector<int>& nums2, int j, int len2, int k){
if(i >= len1) return nums2[j + k - 1];
if(j >= len2) return nums1[i + k - 1];
if(k == 1) return min(nums1[i], nums2[j]);

int median1 = (i + k/2 - 1) < len1 ? nums1[i + k/2 -1] : INT_MAX;
int median2 = (j + k/2 - 1) < len2 ? nums2[j + k/2 -1] : INT_MAX;

if(median1 < median2)
return findK(nums1, i + k/2, len1, nums2, j, len2, k - k/2);
else
return findK(nums1, i, len1, nums2, j + k/2, len2, k - k/2);
}
};

  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
class Solution:

def findK(self, nums1: List[int], i, len1, nums2: List[int], j, len2, k):
if i >= len1 : return nums2[j + k -1]
if j >= len2 : return nums1[i + k -1]
if k == 1 : return min(nums1[i], nums2[j])

median1 = nums1[i + int(k/2) - 1] if (i + int(k/2) - 1) < len1 else sys.maxsize
median2 = nums2[j + int(k/2) - 1] if (j + int(k/2) - 1) < len2 else sys.maxsize

if median1 < median2:
return self.findK(nums1, i + int(k/2), len1, nums2, j, len2, k - int(k/2))
else:
return self.findK(nums1, i, len1, nums2, j + int(k/2), len2, k - int(k/2))

def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
len1 = len(nums1)
len2 = len(nums2)

leftk = int((len1 + len2 + 1)/2)
rightk = int((len1 + len2 + 2)/2)

return (self.findK(nums1, 0, len1, nums2, 0, len2, leftk)
+ self.findK(nums1, 0, len1, nums2, 0, len2, rightk))/2.0

  java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length, len2 = nums2.length;
int leftk = (len1 + len2 + 1)/2;
int rightk = (len1 + len2 + 2)/2;
return (findK(nums1, 0, len1, nums2, 0, len2, leftk)
+ findK(nums1, 0, len1, nums2, 0, len2, rightk))/2.0;
}
public int findK(int[] nums1, int i, int len1, int[] nums2, int j, int len2, int k){
if(i >= len1) return nums2[j + k - 1];
if(j >= len2) return nums1[i + k - 1];
if(k == 1) return Math.min(nums1[i], nums2[j]);
int median1 = (i + k/2 - 1) < len1 ? nums1[i + k/2 - 1] : Integer.MAX_VALUE;
int median2 = (j + k/2 - 1) < len2 ? nums2[j + k/2 - 1] : Integer.MAX_VALUE;

return median1 < median2 ? findK(nums1, i + k/2, len1, nums2, j, len2, k - k/2)
: findK(nums1, i, len1, nums2, j + k/2, len2, k - k/2);
}
}