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

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

简单来说就是求两个已经排好序的数组的中位数

代码

1. 先合并两个数组进行排序，然后求中位数
   public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //先给两个数组进行排序
        int[] datas = new int[nums1.length + nums2.length];
        int i = 0;
        int k = 0;
        int index = 0;
        while (i<nums1.length || k<nums2.length) {
            if(k>=nums2.length) {
                datas[index++] = nums1[i++];
                continue;
            }
            if(i>=nums1.length) {
                datas[index++] = nums2[k++];
                continue;
            }
            if(nums1[i]<nums2[k]) {
                datas[index++] = nums1[i++];
            }else {
                datas[index++] = nums2[k++];
            }
        }
        //取中位数
        if(datas.length%2==0) {
            //取中间两个数，求平均数
            return (datas[datas.length/2 -1] + datas[datas.length/2])/2.0;
        }else {
            //取中间一个数
            if(datas.length == 1) {
                return datas[0];
            }
            return datas[datas.length/2];
        }
    }

2. 已经排好了序，直接按取第几个数这样
  public double findnum2(int[] nums1,int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int i = 0, j = 0, index = 0, len = m + n, loop = len / 2;

        int mid0 = 0, mid1 = 0;
        while (index <= loop) {
            mid0 = mid1;
            if (i < m && j < n) {
                mid1 = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
            } else if (i < m) {
                mid1 = nums1[i++];
            } else {
                mid1 = nums2[j++];
            }
            ++index;
        }

        if (len % 2 == 0) {
            return (mid0 + mid1) / 2.0;
        } else {
            return mid1;
        }
    }

第二种方法的逻辑要多想