Study Notes
  • Kuma Blog
  • AI
    • AI-Resources
    • AI-books
    • Prompts
      • Prompts Free Courses
  • Movies
    • 2024
    • 2024
    • 2024
  • Google
    • chunked-palindrome
  • Setup
    • How to add a new user into Ubuntu and setup ssh key?
    • How to set up VSCode remote server connect with browser with Docker
  • kubernetes
  • Books
    • Designing-Data-Intensive-Applications
      • 第一章 — 可靠性,可扩展性,可维护性的应用程序(Reliable, Scalable, and Maintainable Applications)
    • System-Performance
      • Design-Data-Intensive-Application
      • Chapter 2: Methodologies
  • Languages
    • japanese
      • japanese-week
  • Leetcode
    • 30DayChallenge
      • LRU-cache
      • backspace-string-compare
      • binary-tree-maximum-path-sum
      • bitwise-and-number-range
      • check-string-valid-sequence-from-root-to-leaves-path-in-bst
      • construct-binary-search-tree-from-preorder-traversal
      • contiguous-array
      • counting-elements
      • diameter-of-binary-tree
      • first-unique-number
      • group-anagrams
      • jump-game
      • last-stone-weight
      • leftmost-column-with-at-least-a-one
      • longest-common-subsequect
      • maximal-square
      • maximum-subarray
      • middle-of-the-linked-list
      • min-stack
      • minimun-path-sum
      • move-zeroes
      • perform-string-shifts
      • product-of-array-except-itself
      • search-in-rotated-sorted-array
      • subarray-sum-equals-k
      • valid-parenthesis-string
    • English Solution
      • 1168.optimize-water-distribution-in-a-village-en
      • 1171.remove-zero-sum-consecutive-nodes-from-linked-list-en
      • 1177.can-make-palindrome-from-substring-en
      • 1343.number-of-avg-subarr-sizek-greater-or-equal-threshold
      • 1345.jump-game-iv
      • 25.reverse-nodes-in-k-groups-en
      • 474.ones-and-zeros-en
      • 53.maximum-sum-subarray-en
      • 547.friend-circles-en
      • 79.word-search-en
    • May2020Challenge
      • check-if-straight-line
      • cousins-in-binary-tree
      • find-town-judge
      • first-bad-version
      • first-unique-character-in-a-string
      • flood-fill
      • implement-trie
      • jewels-and-stones
      • majority-element
      • maximum-sum-circular-subarray
      • number-complement
      • odd-even-linkedlist
      • ransom-note
      • remove-k-digits
      • single-element-in-sorted-array
      • valid-perfect-square
    • python
      • 000017-Letter-Combinations-of-a-Phone-Number
      • 000032-Longest-Valid-Parentheses
      • 000033-Search-in-Rotated-Sorted-Array
      • 000046-Permutations
      • 000074-Search-a-2D-Matrix
      • 000077-Combinations
      • 000081-Search-in-Rotated-Sorted-Array-II
      • 000137-single-number-ii
      • 000139-Word-Break
      • 000207-courses-schedule
      • 000209-Minimum-Size-Subarray-Sum
      • 000376-wiggle-subsequence
      • 000445-Add-Two-Numbers-II
      • 000486-Predict-the-Winner
      • 000518-Coin-Change-II
      • 000673-Number-of-Longest-Increasing-Subsequence
      • 000688-Knight-Probability-in-Chessboard
      • 000735-Asteroid-Collision
      • 000852-Peak-Index-in-a-Mountain-Array
      • 859-Buddy-Strings
      • 000864-Shortest-Path-to-Get-All-Keys
      • 000920-Number-of-Music-Playlists
      • 001218-Longest-Arithmetic-Subsequence-of-Given-Difference
      • 001235-Maximum-Profit-in-Job-Scheduling
      • 001493-Longest-Subarray-of 1-After-Deleting-One-Element
      • Problem
      • 002024-Maximize-the-Confusion-of-an-Exam
      • 2305-Fair-Distribution-of-Cookies
      • 002616-Minimize-the-Maximum-Difference-of-Pairs
      • 00802-Find-Eventual-Safe-States
    • 中文版解题
      • 1147.longest-chunked-palindrome-decomposition-cn
      • 1168.optimize-water-distribution-in-a-village-cn
      • 1171.remove-zero-sum-consecutive-nodes-from-linked-list-cn
      • 1177.can-make-palindrome-from-substring-cn
      • 215.kth-largest-element-in-an-array-cn
      • 25.reverse-nodes-in-k-groups-cn
      • 30.substring-with-concatenation-of-all-words-cn
      • 4.median-of-two-sorted-array-cn
      • 460.LFU-cache-cn
      • 474.ones-and-zeros-cn
      • 53.maximum-sum-subarray-cn
      • 79.word-search-cn
  • Readings
    • 2020
      • Design-Data-Intensive-Application
      • 亲爱的提奥
      • 理想国
      • 贫穷的本质
Powered by GitBook
On this page
  • 题目地址
  • 题目描述
  • 思路
  • 解法一 - 暴力 (Brute Force)
  • 解法二 - 二分查找 (Binary Search)
  • 关键点分析
  • 代码(Java)

Was this helpful?

  1. Leetcode
  2. 中文版解题

4.median-of-two-sorted-array-cn

Previous30.substring-with-concatenation-of-all-words-cnNext460.LFU-cache-cn

Last updated 5 years ago

Was this helpful?

题目地址

题目描述

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

思路

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

这道题,很容易想到暴力解法,时间复杂度和空间复杂度都是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依次放入新的数组中.

时间复杂度: 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]

时间复杂度: 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

代码(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;
    }
}

解法二 - 二分查找(Binary Search

class MedianSortedTwoArrayBinarySearch {
  public static double findMedianSortedArraysBinarySearch(int[] nums1, int[] nums2) {
     // do binary search for shorter length array 
     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
        int i = lo + (hi - lo) / 2;
        // partition B
        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) {
          // even
          if ((m + n) % 2 == 0) {
            return (double) (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
          } else {
            // odd
            return (double) Math.max(maxLeftA, maxLeftB);
          }
        } else if (maxLeftA > minRightB) {
          hi = i - 1;
        } else {
          lo = i + 1;
        }
      }
      return 0.0;
    }
}

如下图:

Merge的过程如下图。

如图:

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

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

https://leetcode.com/problems/median-of-two-sorted-arrays/
merge two sorted array
partition A,B
median examples
median partition example
median