LeetCode-04-FindMedianSortedArrays

本文最后更新于:a year ago

题目

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.


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

The median is 2.0

Example2

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

The median is (2 + 3)/2 = 2.5

题目大意

给定两个大小为m和n的有序数组nums1和nums2。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m+n))。
你可以假设nums1和nums2不会同时为空。

解题思路

方法一: 二分查找

这一题所用的思想是二分法,才能让我们最后实现的时间复杂度为log,所以我们需要从二分查找去考虑这个问题。具体的解题思路,可以去看看LeetCode官方给的很仔细的解释
寻找两个有序数组的中位数

代码

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
package leetcode;

public class D04_FindMedianSortedArrays {

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length1 = nums1.length, length2 = nums2.length;
int totalLength = length1 + length2;
if (totalLength % 2 == 1) {
int midIndex = totalLength / 2;
double median = getKthElement(nums1, nums2, midIndex + 1);
return median;
} else {
int midIndex1 = totalLength / 2, midIndex2 = totalLength / 2 - 1;
double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
return median;
}
}

private int getKthElement(int[] nums1, int[] nums2, int k) {
int length1 = nums1.length, length2 = nums2.length;
int index1 = 0, index2 = 0;
int kthElement = 0;

while (true) {
//边界情况
if (index1 == length1) {
return nums2[index2 + k - 1];
}
if (index2 == length2) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[index1], nums2[index2]);
}

//正常情况
int half = k / 2;
int newIndex1 = Math.min(index1 + half, length1) - 1;
int newIndex2 = Math.min(index2 + half, length2) - 1;
int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= (newIndex1 - index1 + 1);
index1 = newIndex1 + 1;
} else {
k -= (newIndex2 - index2 + 1);
index2 = newIndex2 + 1;
}
}
}

}

复杂度分析

* 时间复杂度:O(log(m+n)),其中m和n分别是数组nums1和nums2的长度。初始化有 k=(m+n)/2k=(m+n)/2+1, 每一轮循环可以将查找范围减少一半,因此时间复杂度是O(log(m+n))。
* 空间复杂度:O(1)

方法二: 划分数组

这个算法有点难度,所以留下以后来继续深究。