4. Median of Two Sorted Arrays 【Hard】

avatar 2020年08月30日11:18:19 6 2006 views
博主分享免费Java教学视频,B站账号:Java刘哥

Question

Given two sorted arrays nums1 and nums2 of size m and n respectively.

Return the median of the two sorted arrays.

Follow up: The overall run time complexity should be O(log (m+n)).

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

 

Constraints:

  • nums1,length == m
  • nums2,length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000

 

My Answer

class Solution {
     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 合并
        int i = 0, j = 0;
        int m = nums1.length, n = nums2.length;
        int len = m + n;
        int[] nums3 = new int[len];
        while (i < m || j < n) {
            if ((j >= n) || (i < m && nums1[i] < nums2[j])) {
                nums3[i + j] = nums1[i];
                i++;
            } else {
                nums3[i + j] = nums2[j];
                j++;
            }
        }

        // 奇数
        if (len % 2 == 1) {
            return nums3[(len + 1) / 2 - 1];
        } else {
            return (nums3[len / 2] + nums3[len / 2 - 1]) / 2.0;
        }
    }
}

 

  • 微信
  • 交流学习,有偿服务
  • weinxin
  • 博客/Java交流群
  • 资源分享,问题解决,技术交流。群号:590480292
  • weinxin
avatar

发表评论

avatar 登录者:匿名
匿名评论,评论回复后会有邮件通知

  

已通过评论:0   待审核评论数:0