LeetCode第四题

题目：

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)).

You may assume nums1 and nums2 cannot be both empty.

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

思路

• 类似于插入排序
• 设置一个辅助数组，把输入的两个数组重新进行排序
• 中间的数就是中位数
• 总数单数为中间数，偶数为中间两个数的平均数

代码：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
       int max = nums1.length+nums2.length;//计算两个数组的总长度
            int[] nums= new int[max];、、新建辅助数组
            int i=0,j=0;//分别指向两个数组的第一个数
            int k = 0; //记录辅助数组下标
            while (i<nums1.length&&j<nums2.length){
            //从小到大排序
                if (nums1[i] < nums2[j]){
                    nums[k++] = nums1[i++];
                }
                else
                    nums[k++] = nums2[j++];
                }
            while (i < nums1.length){//nums2遍历完
                nums[k++] = nums1[i++];
            }
            while (j < nums2.length){//nums1已经遍历完
                nums[k++] = nums2[j++];
            }
            if (max%2 == 0){//总数为偶数
                return (double)(nums[max/2-1]+nums[max/2])/2;
            }
            return (double)nums[max/2];//总数为基数
    }
}