1.Problem
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)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
2.Translation
给两个各自排好序的数组，然后找出他们两个中的中间值，如示例所示。然后给了时间复杂度的限制。
3.My View
出去开一个大会跑回来还有各种各样的事要做……但是还是先刷一道算法吧。
回来室友说这个很简单，然后做了n久，虽然有了想法，想法是合并->排序，说起来应该达不到n方的复杂度，但是无从下手。
然后室友说用了Python的库函数，排序（数组1+数组2）。
虽然觉得直接调库就没啥意思了，但是还是写了一个调库的，更高端的有空再研究。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
//构建新数组
int[] nums = new int[nums1.length+nums2.length];
//将数组合并（采用arraycopy函数）
if(nums1.length>0&&nums2.length>0){
System.arraycopy(nums1, 0, nums, 0, nums1.length);
System.arraycopy(nums2, 0, nums, nums1.length, nums2.length);
}else if(nums1.length>0&&nums2.length==0){
System.arraycopy(nums1, 0, nums, 0, nums1.length);
}else if(nums2.length>0&&nums1.length==0){
System.arraycopy(nums2, 0, nums, 0, nums2.length);
}
//将数组排序（sort函数）
Arrays.sort(nums);
//返回结果
return (nums[(nums.length-1)/2]+nums[nums.length/2])/2.0;
}
}
这里主要用了arraycopy和sort函数，用来完成数组合并和排序。
当然，嗯，路过打个酱油啦！
于是抽空又写了一个能说的过去的。
不过当然不能跟大神比啦。
连大众算法都没上。
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
//构建新数组
int[] nums = new int[nums1.length+nums2.length];
int num1_len = nums1.length,num2_len = nums2.length;
int i = 0,j = 0,k = 0;
//调整数组访问顺序
if(num1_len > num2_len){
return findMedianSortedArrays(nums2,nums1);
}
while(i<num1_len||j<num2_len){
//余数据处理
if(i<=nums1.length-1&&j>nums2.length-1){
nums[k] = nums1[i];
i++;
k++;
continue;
}
if(i>nums1.length-1&&j<=nums2.length-1){
nums[k] = nums2[j];
j++;
k++;
continue;
}
//正常数据处理
if(nums1[i]<=nums2[j]){
nums[k] = nums1[i];
i++;
}else{
nums[k] = nums2[j];
j++;
}
k++;
}
//结果
return (nums[(nums.length-1)/2]+nums[nums.length/2])/2.0;
}
期间也是遇到大大小小的错误，连续提交了几次才成功。算法的理念就是排序合并，这个想法是源自于数据结构链表合并排序的题目，以前没仔细写过，今天算是拿数组练练手了。
真正官方的，
NB的在下面。
Solution
Put left_A and left_B into one set, and put right_A and right_B into another set.
把A数组分成左右两部分，B数组也分成左右两部分。
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
然后如果我们确保
//左右长度一致
len(left_part)=len(right_part)
//左部分最大值小于右部分最小值
max(left_part)≤min(right_part)
那么我们就会很轻易地得到答案
a = （max（left_part）+ min(right_part)）/2
那么接下来我们要解决的问题就是如何满足这两个条件
//首先我们要求（i是A数组左部分，j是B数组左部分，m是A的长度，
//n是B的长度，那么这样很显然就是让A_left + B_left = A_right+B_right）
i+j=m−i+n−j
//为了确保大小，我们结合刚开始给的表格来看
B[j−1]≤A[i] and A[i−1]≤B[j]
and then？
Searching i in [0,m], to find an object i such that:
//在【0，m】区间搜索一个满足条件的i
B[j−1]≤A[i] and A[i−1]≤B[j], where j = （m+n+1）/2 - i
这里一定要确保j是非负数，那么要求就是m要比n小，否则可能会因为m/2太大导致j是负数。
同时我们在分析这种情况的时候，不能忽视了一些极端数据，比如说空数组，重复数据等
官方给出的解释是，当我们比较这些情况的时候
B[j−1]≤A[i] and A[i−1]≤B[j], where j = （m+n+1）/2 - i
如果他们不存在（数据），可以直接空过去
那么在搜索的过程中就出现了三种情况
(j=0 or i = m or B[j−1]≤A[i]) and
i = 0 or j=n or A[i−1]≤B[j])
Means ii is perfect, we can stop searching.
(j > 0 and i <m and B[j−1]>A[i])
Means ii is too small, we must increase it.
(i>0 and j<n and A[i−1]>B[j])
Means ii is too big, we must decrease it.
最后是Code
public double findMedianSortedArrays(int[] A, int[] B) {
//获取长度
int m = A.length;
int n = B.length;
//确保长度m<n(当然在这里我们也可以用递归来实现，不过效率会低一点)
if (m > n) {
int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp;
}
//初始化变量
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
//循环检查A数组
while (iMin <= iMax) {
//i是A数组中心
int i = (iMin + iMax) / 2;
//J也就是我们公式里的j
int j = halfLen - i;
//接下来就是我们的三种情况
//通过调整imin和imax两个值来确定i，j的位置，
//也就是确保分片的合理性
if (i < iMax && B[j-1] > A[i]){
iMin = iMin + 1; // i is too small
}
else if (i > iMin && A[i-1] > B[j]) {
iMax = iMax - 1; // i is too big
}
//当i是一个合适的切片点的时候，开始查找右片最小值和左片最大值
else { // i is perfect
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
//奇数个直接返回中心点
if ( (m + n) % 2 == 1 ) { return maxLeft; }
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }
//返回中值
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
这个算法核心的地方还是在于分片。
同时这个算法也源自于高中的中值概念，通过排除最小最大值来得到中值。
更多优秀算法建议去LeetCode查看。
