题目
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
示例 1:
nums1 = [1, 3] nums2 = [2]中位数是 2.0
示例 2:
nums1 = [1, 2] nums2 = [3, 4]中位数是 (2 + 3)/2 = 2.5
分析
两个有序数组，找中位数，要求时间复杂度位log（m+n），我写出来的是（m+n）/2。
类似于将两个有序数组重新排列成一个新的有序数组，只不过排列到一半的时候就可以停止了。
还有数组长度之和m+n的是奇是偶要分开来讨论，因为偶数位的中位数是两个相加/2。
用了不少变量做中间存储，空间复杂度o（1）。
要注意nums1数组遍历完之后，nums2数组还有数字没有遍历的情况。
代码量有些多，代码也有些乱，一心光想着睡觉了。不过思路还是比较简单哒。
代码
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;double temp = 0;if ((len1 + len2) % 2 == 0){int mid = (len1 + len2) / 2;int mid2= mid+1;int i = 0; int j = 0;for (; i < len1 && j < len2; ) {int num = 0;if (nums1[i] <= nums2[j]){num = nums1[i];i ++;}else{num = nums2[j];j++;}mid --; mid2 --;if ( 0 == mid || 0 == mid2){ temp += num;if (mid2==0)break;}}if (mid > 0 || mid2 > 0){while (i < len1){mid --; mid2 --;if (mid == 0 || mid2 == 0) temp += nums1[i];i ++;}while (j < len2){mid --; mid2 --;if (mid == 0 || mid2 == 0) temp += nums2[j];j ++;}}return temp/2;}else{int mid = (len1+len2) /2 + 1;int i = 0; int j = 0;for (; i < len1 && j < len2;) {int num = 0;if (nums1[i] <= nums2[j]){num = nums1[i];i ++;}else{num = nums2[j];j++;}mid --;if ( 0 == mid ){temp = num;break;}}if (mid > 0){while (i < len1){mid --;if (mid == 0 ){temp = nums1[i];break;}i ++;}while (j < len2){mid --;if (mid == 0){temp = nums2[j];break;}j ++;}}return temp;}}
}