题目描述：
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
解法一：虽然不符合时间复杂度要求，但是为了说明一下思路，还是cover一下，本地调试和提交都通过了，貌似leetcode缺少复杂度分析机制。
思路：两个排好序的数组，将两个数组合并成一个有序数组，若大数组的长度为奇数，则中位数为大数组中间的那个数，否则中位数为索引值分别是(0+arr.length)和(0+arr.length+1)之和的平均值
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
return getMedian(nums1,m,nums2,n);
}
private double getMedian(int[] nums1, int m, int[] nums2, int n) {
int i = 0;
int j = 0;
int k = 0;
int[] resultArr = new int[m + n];
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
resultArr[k++] = nums1[i++];
} else {
resultArr[k++] = nums2[j++];
}
}
while (i < m) {
resultArr[k++] = nums1[i++];
}
while (j < n) {
resultArr[k++] = nums2[j++];
}
int rn = k-1;
if (rn % 2 == 0) {
return resultArr[rn / 2] * 1.0 ;
} else {
return (resultArr[rn / 2] + resultArr[rn / 2 + 1]) * 1.0 / 2;
}
}
}
复杂度分析：
~时间复杂度：O(m+n)
~空间复杂度：O(m+n)
解法二：递归
思路：
两个有序数组求中位数，问题一般化为，求两个有序数组的第k个数，当k = (m+n)/2时为原问题的解。怎么求第k个数？分别求出第一个和第二个数组的第 k / 2个数 a 和 b，然后比较 a 和 b，当a < b ，说明第 k 个数位于 a数组的第 k / 2个数后半段，或者b数组的 第 k / 2 个数前半段，问题规模缩小了一半，然后递归处理就行。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
//当nums1数组为空的时候
if (m == 0) {
//两个数组的中位数完全取决于数组nums2了
if (n % 2 == 1) {
return nums2[n / 2] * 1.0;
}
return (nums2[n / 2] + nums2[n / 2 -1]) / 2.0;
}
//当nums2数组为空的时候
if (n == 0) {
if (m % 2 == 1) {
return nums1[m / 2] * 1.0;
}
return (nums1[m / 2] + nums1[m / 2 - 1]) / 2.0;
}
//大数组的总长度m+n
int total = m + n;
//数组长度为奇数,则在数组中寻找第total/2+1个数
if (total % 2 == 1) {
return find_kth(nums1, 0, nums2, 0, total / 2 + 1);
}
return (find_kth(nums1, 0, nums2, 0, total / 2) + find_kth(nums1, 0, nums2, 0, total / 2 + 1)) / 2.0;
}
private static double find_kth(int[] nums1, int a_begin, int[] nums2, int b_begin, int k) {
//当a_begin或b_begin超过数组长度，则第k个数为另外一个数组第k个数
if (a_begin >= nums1.length) {
return nums2[b_begin + k - 1];
}
//同理
if (b_begin >= nums2.length) {
return nums1[a_begin + k - 1];
}
//递归结束条件，每个数组中都找其第一个元素,使用递归，必须声明递归结束条件
if (k == 1) {
return Math.min(nums1[a_begin], nums2[b_begin]);
}
//定义mid_a和mid_b分别代表两个数组中的第k/2个数
int mid_a = Integer.MAX_VALUE;
int mid_b = Integer.MAX_VALUE;
if (a_begin + k / 2 - 1 < nums1.length) {
mid_a = nums1[a_begin + k / 2 - 1];
}
if (b_begin + k / 2 - 1 < nums2.length) {
mid_b = nums2[b_begin + k / 2 - 1];
}
//如果nums1数组的第 k / 2 个数小于nums2数组的第 k / 2 个数，表示总的第 k 个数位于 nums1的第k / 2个数的后半
// 段，或者是nums2的第 k / 2个数的前半段，由于范围缩小了 k / 2 个数，此时总的第 k 个数实际上等于新的范围内
// 的第k - k / 2个数，依次递归
if (mid_a < mid_b) {
return find_kth(nums1, a_begin + k / 2, nums2, b_begin, k - k / 2);
}
return find_kth(nums1, a_begin, nums2, b_begin + k / 2, k - k / 2);
}
}
复杂度分析：
~时间复杂度： O(log(m+n))