ACM之LeetCode中Median of Two Sorted Arrays

原题信息：

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我自己的理解：
有两个有序的数组nums1和nums2，长度分别为m和n。找到两个有序数组的中间值。整个运行的时间复杂度为O(log(m+n))。然后在看看题目中给的两个例子，大致思路就有了。
【分析】：
（1）首先把两个有序数组合并成一个数组。
（2）在对合并的数组进行排序。
（3）找出合并后数组的中间值，即为所求答案。
下面是可以AC的java代码:
package test;import java.util.Arrays;public class MedianOfTwoSortedArrays {	public static void main(String[] args) {     		int[] a={1,2};    		int[] b={3,4};    		MedianOfTwoSortedArrays medianOfTwoSortedArrays=new MedianOfTwoSortedArrays();     		System.out.PRint(medianOfTwoSortedArrays.findMedianSortedArrays(a, b));	}		 public double findMedianSortedArrays(int[] nums1, int[] nums2) {		 int[] combine=concat(nums1,nums2);		 Arrays.sort(combine);  //合并后的数组进行排序		 if((0+combine.length-1)%2==0){		       return (double)combine[(combine.length-1)/2];		  }else {		       int temp=(combine.length-1)/2;		        return (double)(combine[temp]+combine[temp+1])/2;		  }     	   }	 	 /**	  * 将两个有序的数组合并成一个数组	  * @param first 第一个数组	  * @param second 第二个数组	  * @return  合并后的数组	  */	 public int[] concat(int[] first,int[] second){		 int[] sum=new int[first.length+second.length];		 System.arraycopy(first, 0, sum, 0, first.length);		 System.arraycopy(second, 0, sum, first.length, second.length);		 return sum;	 }}当然AC了，还是要多看看高手们的代码，看看自己还差多远。这不看不知道，一看还看出问题了。题目要求的时间复杂度是O(log(m+n))。我分析了自己上边的代码时间复杂度是O(nlogn)。写的这个算法不是很严谨呢！所以，抱着科学要严谨的态度，我又写了另外一种算法。
【思路】把本题的问题转换成求第k小数的问题。这个解题思路 ，网上有很多详细的解析，我就不详细写了。