概述
作为复杂题的第一题(Median of Two Sorted Arrays)，在时间复杂度为O(log (m+n))（
m，n均为数组长度）的要求之下，求两个已排序数组的中位数。
分析
首先中位数的定义可以在 WikiPedia 上了解到。在已排序的前提下，即奇数元素个数的数组，为中间值；偶数元素个数的数组则为中间二值的算数平均数。
那么两个序列求中位数，可以考虑先将二者合并排序之后，进行中位数的求值。
考虑到两数组已经排序，那么我们所需要做的就是进行一次归并排序。
归并排序作为一个相当稳定的排序方式，在时间复杂度上能够满足需求。
考虑到虽然数组是排序数组，但是并没有说明是升序或是降序，无妨，如果是降序，那么将下标从尾部开始即可，但是个人测试，应该没有出现这类 case 。
解法
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
69
70
71
72
73
74
75
76
77
78
79
80
81
| public class Solution {
private static final int ASC = 0;
private static final int DESC = 1;
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
double median = 0;
if (nums1.length + nums2.length == 0) {
return 0;
}
if (nums1.length == 1 && nums2.length == 1) {
return (nums1[0] + nums2[0]) / 2.0;
}
int[] mergedNums = new int[nums1.length + nums2.length];
int i = 0;
int j = 0;
int nums1order = (nums1.length >= 2 && nums1[0] > nums1[1]) ? DESC : ASC;
int nums2order = (nums2.length >= 2 && nums2[0] > nums2[1]) ? DESC : ASC;
int mergedIdx = 0;
for (;i < nums1.length || j < nums2.length;) {
int realI = i;
int realJ = j;
if (i >= nums1.length) {
mergedNums[mergedIdx] = nums2[realJ];
++j;
++mergedIdx;
continue;
}
if (j >= nums2.length) {
mergedNums[mergedIdx] = nums1[realI];
++mergedIdx;
++i;
continue;
}
int iVal = nums1[realI];
int jVal = nums2[realJ];
if (iVal == jVal) {
mergedNums[mergedIdx] = iVal;
++mergedIdx;
mergedNums[mergedIdx] = jVal;
++mergedIdx;
++i;
++j;
continue;
}
if (iVal > jVal) {
mergedNums[mergedIdx] = jVal;
++mergedIdx;
++j;
continue;
}
if (iVal < jVal) {
mergedNums[mergedIdx] = iVal;
++mergedIdx;
++i;
}
}
int mergedSize = mergedNums.length;
int medianIdx = (mergedSize + 1) / 2 - 1;
if (mergedSize % 2 == 1) {
median = mergedNums[medianIdx];
} else {
medianIdx = mergedIdx / 2;
median = (mergedNums[medianIdx] + mergedNums[medianIdx - 1]) / 2.0;
}
return median;
}
}
|