Median of Two Sorted Arrays

计算机中的算法到底研究的是技巧还是一种思维方式。

分析算法已知条件如下： - 两个有序数组 - 中位数：奇数取中间值偶数取中间两个数的平均数（浮点型）

---

直接思路

public class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int length=nums1.length+nums2.length; boolean odd=length%2==1; int index=0; if(odd){ index=length/2; }else{ index=length/2-1; } System.out.print(index); return intAtIndex(nums1,nums2,index,odd); } public double intAtIndex(int[] nums1,int[] nums2,int index,boolean odd){ int temp=0; int left=0; int right=0; double result=0; while(temp<index){ if(left<nums1.length&&right<nums2.length&&nums1[left]<nums2[right]){ left++; }else if(left==nums1.length){ right++; }else if(right==nums2.length){ left++; }else{ right++; } temp++; } if(odd){ if(left==nums1.length){ result=nums2[right]; }else if(right==nums2.length){ result=nums1[left]; }else{ result=nums1[left]<nums2[right]?nums1[left]:nums2[right]; } }else{ String temp1=findNext(nums1,nums2,left,right); String[] temps=temp1.split(","); Integer leftNumber=Integer.parseInt(temps[0]); String temp2=findNext(nums1,nums2,Integer.parseInt(temps[1]),Integer.parseInt(temps[2])); Integer rightNumber=Integer.parseInt(temp2.split(",")[0]); result=(leftNumber+rightNumber)/2.0; } return result; } private String findNext(int[] nums1,int[] nums2,int left,int right){ int result=0; if(left==nums1.length){ result= nums2[right]; right++; } else if(right==nums2.length){ result= nums1[left]; left++; }else if(nums1[left]<nums2[right]){ result=nums1[left]; left++; }else{ result= nums2[right]; right++; } return result+","+left+","+right; } }

报错：运行时间超时。在本程序中已经尽量只遍历对数组只遍历一次，能优化的点只有第三个函数。

本以为时间复杂度为O(n)的算法已经接近极致了，没想到其实对有序数列来说O(logN),O(1)都是可以优化的目标。到网上翻了一些算法解决方案，主要思路如下：

将找中位数抽象为找第k小的数，既然已经告知两个数组有序，那就要充分利用此有效信息，减少算法的遍历范围。缩小范围从二分法开始：两边同时二分法，A[k/2]与B[k/2]进行比较，较小者的前半段可以不再比较，以此类推，逐渐跳跃式的减少对搜索空间的遍历。

看到我的第三个函数我只想说业务代码写多了，脑子里都是渣呀。优化后的算法如下：

public class Solution { public double findMedianSortedArrays(int A[], int B[]) { int len = A.length + B.length; if (len % 2 == 1) { return findKth(A, 0, B, 0, len / 2 + 1); } return ( findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1) ) / 2.0; } // find kth number of two sorted array public static int findKth(int[] A, int A_start, int[] B, int B_start, int k){ if (A_start >= A.length) { return B[B_start + k - 1]; } if (B_start >= B.length) { return A[A_start + k - 1]; } if (k == 1) { return Math.min(A[A_start], B[B_start]); } int A_key = A_start + k / 2 - 1 < A.length ? A[A_start + k / 2 - 1] : Integer.MAX_VALUE; //此处为算法的技巧点， //本质比较的是第k/2个数，当index越界时，认为其中位数为最大整数，不在此轮进行比较A数组的元素，而是去比较B数组的元素，从而减小K的取值。 //最大整数的引用，可以规范算法的形式，思想以后可以借鉴 int B_key = B_start + k / 2 - 1 < B.length ? B[B_start + k / 2 - 1] : Integer.MAX_VALUE; if (A_key < B_key) { return findKth(A, A_start + k / 2, B, B_start, k - k / 2); } else { return findKth(A, A_start, B, B_start + k / 2, k - k / 2); } } }

优化算法来源：http://www.jiuzhang.com/solutions/median-of-two-sorted-arrays/