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

快来打我* 2022-09-08 03:56 212阅读 0赞

[https://leetcode-cn.com/problems/median-of-two-sorted-arrays/][https_leetcode-cn.com_problems_median-of-two-sorted-arrays]

难度困难4407

给定两个大小分别为 `m` 和 `n` 的正序（从小到大）数组 `nums1` 和 `nums2`。请你找出并返回这两个正序数组的 **中位数** 。

**示例 1：**

输入：nums1 = [1,3], nums2 = [2]
    输出：2.00000
    解释：合并数组 = [1,2,3] ，中位数 2

**示例 2：**

输入：nums1 = [1,2], nums2 = [3,4]
    输出：2.50000
    解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

**示例 3：**

输入：nums1 = [0,0], nums2 = [0,0]
    输出：0.00000

**示例 4：**

输入：nums1 = [], nums2 = [1]
    输出：1.00000

**示例 5：**

输入：nums1 = [2], nums2 = []
    输出：2.00000

**提示：**

*  `nums1.length == m`
 *  `nums2.length == n`
 *  `0 <= m <= 1000`
 *  `0 <= n <= 1000`
 *  `1 <= m + n <= 2000`
 *  `-106 <= nums1[i], nums2[i] <= 106`

**进阶：**你能设计一个时间复杂度为 `O(log (m+n))` 的算法解决此问题吗？

通过次数483,627提交次数1,188,624

class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int [] n = new int[nums1.length+nums2.length];
            int i=0,j=0,k=0;
            while(i<nums1.length && j<nums2.length)
            {
               if(nums1[i]<=nums2[j])
               {
                   n[k++]= nums1[i++];
               }
               else n[k++] = nums2[j++];
            }
            while(i<nums1.length)
            {
                n[k++]= nums1[i++];
            }
            while(j<nums2.length)
            {
                n[k++] = nums2[j++];
            }
            if((nums1.length+nums2.length)%2==0) return (n[n.length/2]+n[n.length/2-1])/2.0;
            else return n[n.length/2];
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_20_color_FFFFFF_t_70_g_se_x_16][]

class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int [] n = new int[nums1.length+nums2.length];
            int i=0,j=0,k=0,x=n.length/2;
            while(i<nums1.length && j<nums2.length)
            {
               if(nums1[i]<=nums2[j])
               {
                   n[k++]= nums1[i++];
                   
               }
               else n[k++] = nums2[j++];
               if(x<k) break;
            }
            while(i<nums1.length && x>=k)
            {
                n[k++]= nums1[i++];
                
            }
            while(j<nums2.length && x>=k)
            {
                n[k++] = nums2[j++];
            }
            if((nums1.length+nums2.length)%2==0) return (n[n.length/2]+n[n.length/2-1])/2.0;
            else return n[n.length/2];
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

[https_leetcode-cn.com_problems_median-of-two-sorted-arrays]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/eb9ca21a22dc412c80b7f3bac6a2348d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/52d8c00f34fc4bed87f9de778c2c9bc9.png