LeetCode
leetcode
2018/01/19
问题描述
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
思路
- 合并两个数组，然后找到中间值。这是最笨的方法。
- 题目没有要求输出合并后的数组，所以没必要全部比较，可以记录比较的长度，只要达到中间长度就停止。
- 进一步优化，不用辅助数组，试探性查找。
代码
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2=nums2.size();
int len = (len1+len2)/2, f = (len1+len2)%2;
vector<int> tem;
double ans = 0;
int i = 0, j= 0;
while(i<len1&&j<len2&&i+j<len+1){
if(nums1[i]>nums2[j]){
tem.push_back(nums2[j]);
j++;
}else{
tem.push_back(nums1[i]);
i++;
}
cout<<i<<" "<<j<<endl;
}
while(i+j<len+1){
if(i<len1){
tem.push_back(nums1[i]);
i++;
}
if(j<len2){
tem.push_back(nums2[j]);
j++;
}
cout<<i<<" "<<j<<endl;
}
cout<<i<<" "<<j<<" "<<len<<endl;
if(f>0){
ans = tem[len];
}else{
ans = double(tem[len-1]+tem[len])/2;
}
return ans;
}
|
不用vector1
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2=nums2.size();
int len = (len1+len2)/2, f = (len1+len2)%2;
double ans = 0, tem = 0;
int i = 0, j= 0;
while(i<len1&&j<len2&&i+j<len+1){
if(nums1[i]>nums2[j]){
if(i+j==len-1){
tem = nums2[j];
}
if(i+j==len){
ans = nums2[j];
}
j++;
}else{
if(i+j==len-1){
tem = nums1[i];
}
if(i+j==len){
ans = nums1[i];
}
i++;
}
cout<<i<<" "<<j<<endl;
}
while(i+j<len+1){
if(i<len1){
if(i+j==len-1){
tem = nums1[i];
}
if(i+j==len){
ans = nums1[i];
}
i++;
}
if(j<len2){
if(i+j==len-1){
tem = nums2[j];
}
if(i+j==len){
ans = nums2[j];
}
j++;
}
cout<<i<<" "<<j<<endl;
}
cout<<i<<" "<<j<<" "<<len<<endl;
if(f>0){
return ans;
}else{
return (ans+tem)/2;
}
}
|
进一步优化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
29
30
31
32
33
34
35
36
|
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2=nums2.size();
if(len1>len2){
vector<int> tem = nums1; nums1 = nums2; nums2=tem;
int t = len1; len1 = len2; len2 = t;
}
int iMin = 0, iMax = len1, half = (len1+len2+1)/2;
while(iMin <= iMax){
int i = (iMin + iMax)/2;
int j = half - i;
if (i < iMax && nums2[j-1] > nums1[i]){
iMin = iMin + 1;
}
else if (i > iMin && nums1[i-1] > nums2[j]) {
iMax = iMax - 1;
}
else {
int maxLeft = 0;
if (i == 0) { maxLeft =nums2[j-1]; }
else if (j == 0) { maxLeft = nums1[i-1]; }
else { maxLeft = max(nums1[i-1], nums2[j-1]); }
if ( (len1 + len2) % 2 == 1 ) { return maxLeft; }
int minRight = 0;
if (i == len1) { minRight = nums2[j]; }
else if (j == len2) { minRight = nums1[i]; }
else { minRight = min(nums2[j], nums1[i]); }
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
|
