1. 首页

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

题目描述

给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

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

示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
来源:Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/

示例 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

难度:

  • 难度:困难
  • 支持语言:JavaScriptJavaPython

相关标签

相关企业

  • 阿里
  • 百度
  • 腾讯

思路

首先了解一下 Median 的概念,一个数组中 median 就是把数组分成左右等分的中位数。

如下图:
image.png

这道题,很容易想到暴力解法,时间复杂度和空间复杂度都是O(m+n), 不符合题中给出O(log(m+n))时间复杂度的要求。
我们可以从简单的解法入手,试了一下,暴力解法也是可以被 Leetcode Accept 的. 分析中会给出两种解法,暴力求解和二分解法。

解法一 – 暴力 (Brute Force)

暴力解主要是要 merge 两个排序的数组(A,B)成一个排序的数组。

用两个pointer(i,j)i 从数组A起始位置开始,即i=0开始,j 从数组B起始位置, 即j=0开始.
一一比较 A[i] 和 B[j],

  1. 如果A[i] <= B[j], 则把A[i] 放入新的数组中,i 往后移一位,即 i+1.
  2. 如果A[i] > B[j], 则把B[j] 放入新的数组中,j 往后移一位,即 j+1.
  3. 重复步骤#1 和 #2,直到i移到A最后,或者j移到B最后。
  4. 如果j移动到B数组最后,那么直接把剩下的所有A依次放入新的数组中.
  5. 如果i移动到A数组最后,那么直接把剩下的所有B依次放入新的数组中.

Merge 的过程如下图。
image.png

时间复杂度: O(m+n) - m is length of A, n is length of B

空间复杂度: O(m+n)

解法二 – 二分查找 (Binary Search)

由于题中给出的数组都是排好序的,在排好序的数组中查找很容易想到可以用二分查找(Binary Search), 这里对数组长度小的做二分,
保证数组 A 和 数组 B 做 partition 之后

len(Aleft)+len(Bleft)=(m+n+1)/2 - m是数组A的长度, n是数组B的长度

对数组 A 的做 partition 的位置是区间[0,m]

如图:
image.png

下图给出几种不同情况的例子(注意但左边或者右边没有元素的时候,左边用INF_MIN,右边用INF_MAX表示左右的元素:
image.png

下图给出具体做的 partition 解题的例子步骤,
image.png

时间复杂度: O(log(min(m, n)) - m is length of A, n is length of B

空间复杂度: O(1) – 这里没有用额外的空间

关键点分析

  1. 暴力求解,在线性时间内 merge 两个排好序的数组成一个数组。
  2. 二分查找,关键点在于
  • 要 partition 两个排好序的数组成左右两等份,partition 需要满足len(Aleft)+len(Bleft)=(m+n+1)/2 - m是数组A的长度, n是数组B的长度

  • 并且 partition 后 A 左边最大(maxLeftA), A 右边最小(minRightA), B 左边最大(maxLeftB), B 右边最小(minRightB) 满足
    (maxLeftA <= minRightB && maxLeftB <= minRightA)

有了这两个条件,那么 median 就在这四个数中,根据奇数或者是偶数,

奇数:
median = max(maxLeftA, maxLeftB)
偶数:
median = (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2

Js中文网 – 前端进阶资源教程 www.javascriptC.com,typescript 中文文档
Javascript中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js……等,以帮助开发者成长为愿景的社区

复杂度分析

  • 时间复杂度:$O(log(min(m, n)))$
  • 空间复杂度:$O(log(min(m, n)))$

代码

Java 实现

解法一 – 暴力解法(Brute force)

class MedianTwoSortedArrayBruteForce {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      int[] newArr = mergeTwoSortedArray(nums1, nums2);
      int n = newArr.length;
      if (n % 2 == 0) {
        // even
        return (double) (newArr[n / 2] + newArr[n / 2 - 1]) / 2;
      } else {
        // odd
        return (double) newArr[n / 2];
      }
    }
    private int[] mergeTwoSortedArray(int[] nums1, int[] nums2) {
      int m = nums1.length;
      int n = nums2.length;
      int[] res = new int[m + n];
      int i = 0;
      int j = 0;
      int idx = 0;
      while (i < m && j < n) {
        if (nums1[i] <= nums2[j]) {
          res[idx++] = nums1[i++];
        } else {
          res[idx++] = nums2[j++];
        }
      }
      while (i < m) {
        res[idx++] = nums1[i++];
      }
      while (j < n) {
        res[idx++] = nums2[j++];
      }
      return res;
    }
}
/**
*  @作者:windliang
*  @链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
*/
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int[] nums;
    int m = nums1.length;
    int n = nums2.length;
    nums = new int[m + n];
    if (m == 0) {
        if (n % 2 == 0) {
            return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
        } else {

            return nums2[n / 2];
        }
    }
    if (n == 0) {
        if (m % 2 == 0) {
            return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
        } else {
            return nums1[m / 2];
        }
    }

    int count = 0;
    int i = 0, j = 0;
    while (count != (m + n)) {
        if (i == m) {
            while (j != n) {
                nums[count++] = nums2[j++];
            }
            break;
        }
        if (j == n) {
            while (i != m) {
                nums[count++] = nums1[i++];
            }
            break;
        }

        if (nums1[i] < nums2[j]) {
            nums[count++] = nums1[i++];
        } else {
            nums[count++] = nums2[j++];
        }
    }

    if (count % 2 == 0) {
        return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
    } else {
        return nums[count / 2];
    }
}

//还有另一种解法

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    //将偶数和奇数的情况合并,如果是奇数,会求两次同样的 k 。
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}

private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
    int len1 = end1 - start1 + 1;
    int len2 = end2 - start2 + 1;
    //让 len1 的长度小于 len2,这样就能保证如果有数组空了,一定是 len1
    if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
    if (len1 == 0) return nums2[start2 + k - 1];

    if (k == 1) return Math.min(nums1[start1], nums2[start2]);

    int i = start1 + Math.min(len1, k / 2) - 1;
    int j = start2 + Math.min(len2, k / 2) - 1;

    if (nums1[i] > nums2[j]) {
        return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
    }
    else {
        return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
    }
}

JavaScript 实现

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  // 归并排序
  const merged = [];
  let i = 0;
  let j = 0;
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] < nums2[j]) {
      merged.push(nums1[i++]);
    } else {
      merged.push(nums2[j++]);
    }
  }
  while (i < nums1.length) {
    merged.push(nums1[i++]);
  }
  while (j < nums2.length) {
    merged.push(nums2[j++]);
  }
  /* 来源:Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/ */

  const { length } = merged;
  return length % 2 === 1
    ? merged[Math.floor(length / 2)]
    : (merged[length / 2] + merged[length / 2 - 1]) / 2;
};

复杂度分析

  • 时间复杂度:$O(max(m, n))$
  • 空间复杂度:$O(m + n)$

解法二 – 二分查找(Binary Search)

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:前端中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * 二分解法
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  // make sure to do binary search for shorten array
  if (nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1];
  }
  const m = nums1.length;
  const n = nums2.length;
  let low = 0;
  let high = m;
  while (low <= high) {
    const i = low + Math.floor((high - low) / 2);
    const j = Math.floor((m + n + 1) / 2) - i;

    const maxLeftA = i === 0 ? -Infinity : nums1[i - 1];
    const minRightA = i === m ? Infinity : nums1[i];
    const maxLeftB = j === 0 ? -Infinity : nums2[j - 1];
    const minRightB = j === n ? Infinity : nums2[j];
  /* 来源:Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/ */
    if (maxLeftA <= minRightB && minRightA >= maxLeftB) {
      return (m + n) % 2 === 1
        ? Math.max(maxLeftA, maxLeftB)
        : (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
    } else if (maxLeftA > minRightB) {
      high = i - 1;
    } else {
      low = low + 1;
    }
  }
};
class MedianSortedTwoArrayBinarySearch {
  public static double findMedianSortedArraysBinarySearch(int[] nums1, int[] nums2) {
     // do binary search for shorter length array, make sure time complexity log(min(m,n)).
     if (nums1.length > nums2.length) {
        return findMedianSortedArraysBinarySearch(nums2, nums1);
      }
      int m = nums1.length;
      int n = nums2.length;
      int lo = 0;
      int hi = m;
      while (lo <= hi) {
        // partition A position i
        int i = lo + (hi - lo) / 2;
        // partition B position j
        int j = (m + n + 1) / 2 - i;

        int maxLeftA = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int minRightA = i == m ? Integer.MAX_VALUE : nums1[i];

        int maxLeftB = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int minRightB = j == n ? Integer.MAX_VALUE : nums2[j];

        if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
          // total length is even
          /* 来源:Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/ */
          if ((m + n) % 2 == 0) {
            return (double) (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
          } else {
            // total length is odd
            return (double) Math.max(maxLeftA, maxLeftB);
          }
        } else if (maxLeftA > minRightB) {
          // binary search left half
          hi = i - 1;
        } else {
          // binary search right half
          lo = i + 1;
        }
      }
      return 0.0;
    }
}

Python3 实现

  • 这道题如果时间复杂度没有限定在 O(log(m+n))O(log(m+n)),我们可以用 O(m+n)O(m+n) 的算法解决,用两个指针分别指向两个数组,比较指针下的元素大小,一共移动次数为 (m+n + 1)/2,便是中位数。

  • 首先,我们理解什么中位数:指的是该数左右个数相等。

  • 比如:odd : [1,| 2 |,3],2 就是这个数组的中位数,左右两边都只要 1 位;
  • even: [1,| 2, 3 |,4],2,3 就是这个数组的中位数,左右两边 1 位;

  • 那么,现在我们有两个数组:

    num1: [a1,a2,a3,...an]

    nums2: [b1,b2,b3,...bn]

    [nums1[:left1],nums2[:left2] | nums1[left1:], nums2[left2:]]

  • 只要保证左右两边 个数 相同,中位数就在 | 这个边界旁边产生。

  • 如何找边界值,我们可以用二分法,我们先确定 num1m1 个数的左半边,那么 num2 取 m2 = (m+n+1)/2 - m1 的左半边,找到合适的 m1,就用二分法找。

  • [ [a1],[b1,b2,b3] | [a2,..an],[b4,...bn] ]
  • 我们只需要比较 b3 和 a2 的关系的大小,就可以知道这种分法是不是准确的!

  • 例如:我们令:

nums1 = [-1,1,3,5,7,9]

nums2 =[2,4,6,8,10,12,14,16]

  • m1 = 4,m2 = 3 ,它的中位数就是median = (num1[m1] + num2[m2])/2

  • 时间复杂度:O(log(min(m,n)))O(log(min(m,n)))

  • 对于代码中边界情况,大家需要自己琢磨。


# @作者:powcai # @链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/shuang-zhi-zhen-by-powcai/ class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: n1 = len(nums1) n2 = len(nums2) if n1 > n2: return self.findMedianSortedArrays(nums2,nums1) k = (n1 + n2 + 1)//2 left = 0 right = n1 while left < right : m1 = left +(right - left)//2 m2 = k - m1 if nums1[m1] < nums2[m2-1]: left = m1 + 1 else: right = m1 m1 = left m2 = k - m1 c1 = max(nums1[m1-1] if m1 > 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf") ) if (n1 + n2) % 2 == 1: return c1 c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2 <n2 else float("inf")) return (c1 + c2) / 2

# @作者:ltzp # @链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/hen-hao-li-jie-de-si-lu-by-ltzp/ class Solution(object): def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ res = 0.0 # 来源:Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/ new_array = [] m = len(nums1) n = len(nums2) length = m + n mid = 0 if length & 1: mid = int(length//2) else: mid = int(length/2) i,j = 0,0 while len(new_array) -1 < mid: if i < m and j < n : if nums1[i] < nums2[j]: new_array.append(nums1[i]) i+=1 continue if nums1[i] >= nums2[j]: new_array.append(nums2[j]) j+=1 continue if i == m and j < n: while j < n and len(new_array) -1 < mid: new_array.append(nums2[j]) j+=1 if i < m and j == n: while i < m and len(new_array) -1 < mid: new_array.append(nums1[i]) i+=1 if length & 1: res = new_array[mid] else: res = (new_array[mid-1] + new_array[mid])/2.0 return res

# 作者:yinchuan # 链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/tong-su-yi-dong-shi-xian-qi-lai-ye-jian-dan-de-si-/ class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: length = len(nums1) + len(nums2) i = 0 # 循环次数 pre = None # 前一个弹出的数,length为偶数会用到 cur = None while i < length // 2 + 1: n1 = nums1[-1] if nums1 else -float('inf') n2 = nums2[-1] if nums2 else -float('inf') pre = cur cur = nums1.pop() if n1 > n2 else nums2.pop() i += 1 result = cur if length % 2 == 0: result = (result + pre) / 2 return result

其他

更多题解可以访问我的 Js中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 004. 寻找两个正序数组的中位数

链接:https://www.javascriptc.com/4363.html

« LeetCode 005. 最长回文子串
LeetCode 003. 无重复字符的最长子串»
Flutter 中文教程资源

相关推荐

QR code