本文最后更新于: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
| nums1 = [1, 3] nums2 = [2]
The median is 2.0
|
Example2
| 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)/2
或 k=(m+n)/2+1
, 每一轮循环可以将查找范围减少一半,因此时间复杂度是O(log(m+n))。
* 空间复杂度:O(1)。
方法二: 划分数组
这个算法有点难度,所以留下以后来继续深究。