【leetcode-数组】寻找两个正序数组的中位数

【leetcode-数组】寻找两个正序数组的中位数

题目：

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

思路：

求中位数，即求两个数组合并后中间位置的数，但是题目已经给出两个数组是排好序的，所以只需将两个数组的一半之数排序即可。因为是两个已经排好序的数组，所以只需依次从头比较，较小的放入新建的数组之中即可。

java代码：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int sum=nums1.length+nums2.length;
        int nums3[]=new int[sum];
        int i=0,j=0,temp=0;
        double res;
        while(temp<=sum/2)//将一半的数组排序即可
        {
            if(i<nums1.length&&j<nums2.length)//防止数组溢出
            {
                if(nums1[i]<nums2[j])
                {
                    nums3[temp++]=nums1[i++];
                }
                else
                {
                    nums3[temp++]=nums2[j++];
                }
            }
            else if(i>=nums1.length)//其中一个数组到末尾了
            {
                nums3[temp++]=nums2[j++];
            }
            else 
            {
                nums3[temp++]=nums1[i++];
            }
            
        }
        if(sum%2==0)//偶数位个
        {
            res=((double)(nums3[sum/2]+nums3[sum/2-1]))/2; //需要强转一下类型
        }
        else
        {
            res=nums3[sum/2];//奇数位个
            
        }
          
        return res;
     }
  }