目录
给出两个已排序的数列 $nums1$ 和 $nums2$ ，两个数列长度分别为 $m$ 和 $n$ ，返回这两个数列的中位数。总体的时间复杂度应该是 $O(log(m+n))$ 。
例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解析：合并后数列为 [1,2,3]，中位数为 2。
例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解析：合并后数列为 [1,2,3,4]，中位数为（2 + 3）/ 2 = 2.5。
约束条件：
$$\begin{aligned}
nums1.length == m&\\
nums2.length == n&\\
0 <= m <= 1000&\\
0 <= n <= 1000&\\
1 <= m + n <= 2000&\\
-10^6 <= nums1[i], nums2[i] <= 10^6&
\end{aligned}$$
一开始，写的代码比较直观，使用递归方法，一直移动边界，直到可以直接计算中位数
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size)
{
#define get_cn(s, n) \
do \
{ \
if (n % 2 == 0) \
{ \
return (s[n / 2] + s[n / 2 - 1]) / 2.0; \
} \
else \
{ \
return s[n / 2]; \
} \
} while (0);
if (nums1Size == 0)
{
get_cn(nums2, nums2Size);
}
else if (nums2Size == 0)
{
get_cn(nums1, nums1Size);
}
else if (nums1Size == 1 && nums2Size == 1)
{
return (nums1[0] + nums2[0]) / 2.;
}
if (nums1[0] >= nums2[0])
{
nums2++;
nums2Size--;
if (nums2Size == 0)
{
nums1Size--;
get_cn(nums1,nums1Size);
}
else if (nums1[nums1Size - 1] >= nums2[nums2Size - 1])
{
nums1Size--;
}
else
{
nums2Size--;
}
}
else
{
nums1++;
nums1Size--;
if (nums1Size == 0)
{
nums2Size--;
get_cn(nums2,nums2Size);
}
else if (nums1[nums1Size - 1] >= nums2[nums2Size - 1])
{
nums1Size--;
}
else
{
nums2Size--;
}
}
return findMedianSortedArrays(nums1, nums1Size, nums2, nums2Size);
}
|
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size)
{
#define get_cn(s, n) \
do \
{ \
if (n % 2 == 0) \
{ \
return (s[n / 2] + s[n / 2 - 1]) / 2.0; \
} \
else \
{ \
return s[n / 2]; \
} \
} while (0);
while (nums1Size >= 1 && nums2Size >= 1 && nums1Size + nums2Size > 2)
{
if (nums1[0] >= nums2[0])
{
nums2++;
nums2Size--;
}
else
{
nums1++;
nums1Size--;
}
if (nums1[nums1Size - 1] >= nums2[nums2Size - 1])
{
nums1Size--;
}
else
{
nums2Size--;
}
}
if (nums1Size==0){
get_cn(nums2,nums2Size);
}else if (nums2Size==0){
get_cn(nums1,nums1Size);
}else{
return (nums1[0]+nums2[0])/2.0;
}
}
|
C
提交截图(提交时，非现在状态)
完整信息点击此连接查看
上面的算法效率并不高，实际上分析下，其时间复杂度其实是 $O(m+n)$ 。题解要求的复杂度是 $O(log(m+n))$，也即要求不能逐个寻找，应该有某种类似于快速梯度下降的法子，这里实际上二分搜索应该可以考虑下。
二分搜索的递归解法如下:
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
44
45
46
47
48
49
50
| double findKthSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size, int kth)
{
if (nums1Size == 0)
{
return nums2[kth - 1];
}
if (nums2Size == 0)
{
return nums1[kth - 1];
}
if (kth == 1)
{
return nums2[0] > nums1[0] ? nums1[0] : nums2[0];
}
int kth_left_half = kth / 2;
int kth_right_half = kth / 2;
if (nums1Size < kth_left_half)
{
kth_left_half = nums1Size;
}
if (nums2Size < kth_right_half)
{
kth_right_half = nums2Size;
}
if (nums1[kth_left_half - 1] <= nums2[kth_right_half - 1])
{
nums1 += kth_left_half;
nums1Size -= kth_left_half;
kth -= kth_left_half;
}
else if (nums1[kth_left_half - 1] > nums2[kth_right_half - 1])
{
nums2 += kth_right_half;
nums2Size -= kth_right_half;
kth -= kth_right_half;
}
return findKthSortedArrays(nums1, nums1Size, nums2, nums2Size, kth);
}
double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size)
{
// find (nums1Size+nums2Size)/2 th num
int left_kth = (nums1Size+nums2Size+1)/2;
int right_kth = (nums1Size+nums2Size+2)/2;
return (findKthSortedArrays(nums1,nums1Size,nums2,nums2Size,left_kth)+
findKthSortedArrays(nums1,nums1Size,nums2,nums2Size,right_kth))/2.0;
}
|
C
提交截图(提交时，非现在状态)
完整信息点击此连接查看
未完待续。。。解递归方法
