4. 两个排序数组的中位数

Posted on | In
Words count in article: 445 | Reading time ≈ 2

题目

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

你可以假设 nums1 和 nums2 不同时为空。

示例1：

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

中位数是 2.0

示例2：

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

中位数是 (2 + 3)/2 = 2.5

解法

解法一：

将两个数组排序成一个数组，然后求它们的中位数。因为数组是有序的，所以可以遍历一趟得到结果。算法复杂度为O(max(m,n)),与题目要求的不符。

Java

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
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int length1 = nums1.length;
		int length2 = nums2.length;
        int[] result = new int[length1 + length2];
        int index = 0;
        int index1 = 0;
        int index2 = 0;
        while (index1 < length1 && index2 < length2) {
        	if (nums1[index1] < nums2[index2]) {
        		result[index] = nums1[index1];
        		index1++;
        	} else if (nums1[index1] > nums2[index2]) {
        		result[index] = nums2[index2];
        		index2++;
        	} else {
        		result[index++] = nums1[index1];
        		result[index] = nums1[index1];
        		index1++;
        		index2++;
        	}
        	index++;
        }
        while (index1 < length1) {
        	result[index++] = nums1[index1++];
        }
        
        while (index2 < length2) {
        	result[index++] = nums2[index2++];
        }
        
        if (result.length % 2 == 0)
        {
            return (result[result.length / 2] + result[result.length / 2 - 1]) / 2.0;
        }
        else{
        	return result[result.length / 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
class Solution {
public:

    double findKth(int a[], int m, int b[], int n, int k) {
	    if (m > n)
	    	return findKth(b, n, a, m, k);
	    if (m == 0)
	    	return b[k - 1];
	    if (k == 1)
	    	return min(a[0], b[0]);
	    //divide k into two parts
	    int pa = min(k / 2, m), pb = k - pa;
	    if (a[pa - 1] < b[pb - 1])
	    	return findKth(a + pa, m - pa, b, n, k - pa);
	    else if (a[pa - 1] > b[pb - 1])
	    	return findKth(a, m, b + pb, n - pb, k - pb);
    	else
		    return a[pa - 1];
    }

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total = m + n;
		if (total & 0x1)
			return findKth(A, m, B, n, total / 2 + 1);
		else
			return (findKth(A, m, B, n, total / 2)
					+ findKth(A, m, B, n, total / 2 + 1)) / 2;
    }
};
0%