leetcode-4.寻找两个正序数组的中位数

题目

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

样例输入输出

nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

解题思路

这里给出的思路是本渣渣的普通人第一反应思路。
首先我们理解题目中说的中位数，中位数就是简单点说就是一个可以数组中分割成两部分，一办大于它，一半小于它。所以它在数组中的位置一般都是在中间的位置。

好了我们已经知道了中位数的概念，如果求一个数组中的中位数，我们就可以很容易的求出来。直接求中间的下标就行。那么题目中是两个数组呢？我们正常人的思维呢就是合并一个数组，然后求中间的下标就行。但是合并数组的复杂度太大，我们可以只合并到中位数的位置就行，因为我们只要中位数。

这里合并我们需要一点，就是奇偶数的情况。如果我们的数组总长度是奇数的话，那么中位数就是中间的位置，如果是偶数的话，我们就是最中间两个数的和除以2。所以我们应该在结果的时候分情况处理。而在中间记录中位数的时候，我们要记录两个数，一个是奇数的中位数，同时也是偶数那两个数中较大的那一个数，所以我们同时还要再记录一个偶数那两个较小的数。下面直接贴具体的代码，注释也会解释的。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length,len2 = nums2.length;
        int lens = len1 + len2;
        //奇数情况中位数在位置，偶数情况两个数较大的那一个数所在的位置
        int resMedian =  (lens) / 2;
        //用来进行两个数组滑动的指针
        int i = 0, j = 0;
        //中位数（numMedian2）和偶数较小的那一个数（numMedian1）
        double numMedian1 = 0,numMedian2 = 0;
        while(i < len1 || j < len2){
            if(i < len1 && j < len2){
                //两个数组都还有数
                if(nums1[i] < nums2[j]){
                    //两个指针的位置加起来等于我们合并数组中偶数较小的那一个数的位置
                    if(i + j == resMedian - 1) numMedian1 = nums1[i];
                    //两个两个指针的位置加起来等于我们合并数组中奇数要的那个中位数位置
                    if(i + j == resMedian) numMedian2 = nums1[i];
                    ++i;
                }else{
                    if(i + j == resMedian - 1) numMedian1 = nums2[j];
                    if(i + j == resMedian) numMedian2 = nums2[j];
                    ++j;
                }
                //只有nums2还有数
            }else if(j < len2){
                if(i + j == resMedian - 1) numMedian1 = nums2[j];
                if(i + j == resMedian) numMedian2 = nums2[j];
                ++j;
                //只有nums1还有数
            }else if(i < len1){
                if(i + j == resMedian - 1) numMedian1 = nums1[i];
                if(i + j == resMedian) numMedian2 = nums1[i];
                ++i;
            }
        }
        //如果中位数是两个数之和除以2的情况
        if(lens % 2 == 0){
            return (numMedian1 + numMedian2) / 2;
            //如果中位数直接是中间位置的情况
        }else{
            return numMedian2;
        }
    }
}

虽然代码写的有点啰嗦，不过复杂度还行的。