LeetCode刷题——4.寻找两个有序数组的中位数

题目来源：https://leetcode-cn.com/problems/median-of-two-sorted-arrays

题目4：

给定两个大小为 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

解法：
一、首先我想解决该算法的思想是对于两个数组，首先判断两数组长度和的奇偶性。

若为奇数，则取最中间一个数为中位数；使用index1和index2来表示两个数组的起点，若两索引之和小于中位数的索引，则停止继续遍历；在遍历的过程中，如果数组一的值小于数组二的值，则数组一的索引加一遍历，反之数组二的索引加一遍历，当遍历到中位数的索引时，使得中位数为当前遍历到的值，该值即为中位数。

若为偶数，则取中间两个数的平均数为中位数；遍历过程如上，只不过当遍历到中位数索引-1的位置和中位数索引的位置时，把这两个数保存下来，求他两的平均值即为中位数。代码如下：

可是运行时间太长，超过限制，没有得到结果。

二、参考了网上的解法，提交结果通过，代码如下：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int i = 0,j = 0;
        int count = 0;
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] nums = new int[len1+len2];
        if(len1 ==0){
            if(len2%2 ==0)
                return (nums2[len2/2-1]+nums2[len2/2])/2.0;
            else
                return nums2[len2/2];
        }
        if(len2 ==0){
            if(len1%2 ==0)
                return (nums1[len1/2-1]+nums1[len1/2])/2.0;
            else
                return nums1[len1/2];
        }
        while(count!=(len1+len2)){
            if(i==len1){
                while(j!=len2)
                    nums[count++] = nums2[j++];
                break;
            }
            if(j==len2){
                while(i!=len1)
                    nums[count++] = nums1[i++];
                break;
            }
            if(nums1[i]<nums2[j])
                nums[count++] = nums1[i++];
            else
                nums[count++] = nums2[j++];
        }
        if(count%2==0)
            return (nums[count/2-1]+nums[count/2])/2.0;
        else
            return nums[count/2];
    }
}

这个算法的思想较好理解，首先分别判断两个数组是不是空数组，如果一个为空，则直接由另一个去计算中位数，再判断该不为空的数组的奇偶性，分别讨论。

如果两个数组都不为空，则新创建一个数组，根据传入两数组的值大小进行遍历，将较小的一个放入新数组，依次向后进行，如果在遍历过程中，一个数组遍历完了，则单独遍历另一个数组，直到遍历完该数组，最终能够得到一个新数组，在该数组中数的排列是有序的，可直接根据奇偶性得到中位数。

但是该结果的时间复杂度貌似不是O(log(m + n))。

三、符合题目的解法