题目地址(4. 寻找两个正序数组的中位数)
https://leetcode-cn.com/probl...
题目形容
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出这两个正序数组的中位数，并且要求算法的工夫复杂度为 O(log(m + n))。你能够假如 nums1 和 nums2 不会同时为空。 示例 1:nums1 = [1, 3]nums2 = [2]则中位数是 2.0示例 2:nums1 = [1, 2]nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5前置常识
- 中位数
- 分治法
- 二分查找
公司
- 阿里
- 百度
- 腾讯
暴力法
思路
首先理解一下 Median 的概念，一个数组中 median 就是把数组分成左右等分的中位数。
如下图：
晓得了概念，咱们先来看下如何使用暴力法来解决。
试了一下，暴力解法也是能够被 Leetcode Accept 的。
暴力解次要是要 merge 两个排序的数组（A，B）成一个排序的数组。
用两个pointer（i，j），i 从数组A起始地位开始，即i=0开始，j 从数组B起始地位， 即j=0开始.
一一比拟 A[i] 和 B[j],
- 如果
A[i] <= B[j], 则把A[i]放入新的数组中，i 往后移一位，即i+1. - 如果
A[i] > B[j], 则把B[j]放入新的数组中，j 往后移一位，即j+1. - 反复步骤#1 和 #2，直到
i移到A最初，或者j移到B最初。 - 如果
j挪动到B数组最初，那么间接把剩下的所有A顺次放入新的数组中. - 如果
i挪动到A数组最初，那么间接把剩下的所有B顺次放入新的数组中.
整个过程相似归并排序的合并过程
Merge 的过程如下图。
工夫复杂度和空间复杂度都是O(m+n), 不合乎题中给出O(log(m+n))工夫复杂度的要求。
代码
代码反对： Java，JS：
Java Code：
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; }}JS Code:
/** * @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++]); } 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)$
二分查找
思路
如果咱们把上一种办法的最终后果拿进去独自看的话，不难发现最终后果就是 nums1 和 nums 两个数组交织造成的新数组，也就是说 nums1 和 nums2 的绝对地位并不会发生变化，这是本题的要害信息之一。
为了不便形容，无妨假如最终宰割后，数组 nums1 左侧局部是 A，数组 nums2 左侧局部是 B。因为题中给出的数组都是排好序的，在排好序的数组中查找很容易想到能够用二分查找（Binary Search)·, 这里对数组长度小的做二分以缩小工夫复杂度。对较小的数组做二分可行的起因在于如果一个数组的索引 i 确定了，那么另一个数组的索引地位 j 也是确定的，因为 (i+1) + (j+1) 等于 (m + n + 1) / 2，其中 m 是数组 A 的长度， n 是数组 B 的长度。具体来说，咱们能够保障数组 A 和 数组 B 做 partition 之后，len(Aleft)+len(Bleft)=(m+n+1)/2
接下来须要特地留神四个指针：leftp1, rightp1, leftp2, rightp2，别离示意 A 数组宰割点，A 数组宰割点右侧数，B 数组宰割点，B 数组宰割点右侧数。不过这里有两个临界点须要非凡解决：
- 如果宰割点左侧没有数，即宰割点索引是 0，那么其左侧应该设置为无限小。
- 如果宰割点右侧没有数，即宰割点索引是数组长度-1，那么其左侧应该设置为无限大。
如果咱们二分之后满足：leftp1 < rightp2 and leftp2 < rightp1,那么阐明宰割是正确的，间接返回max(leftp1, leftp2)+min(rightp1, rightp2) 即可。否则，阐明宰割有效，咱们须要调整宰割点。
如何调整呢？实际上只须要判断 leftp1 > rightp2 的大小关系即可。如果 leftp1 > rightp2，那么阐明 leftp1 太大了，咱们能够通过放大上界来升高 leftp1，否则咱们须要扩充下界。
外围代码：
if leftp1 > rightp2: hi = mid1 - 1else: lo = mid1 + 1下面的调整上下界的代码是建设在对数组 nums1 进行二分的根底上的，如果咱们对数组 nums2 进行二分，那么相应地须要改为：
if leftp2 > rightp1: hi = mid2 - 1else: lo = mid2 + 1上面咱们通过一个具体的例子来阐明。
比方对数组 A 的做 partition 的地位是区间[0,m]
如图：
下图给出几种不同状况的例子（留神但右边或者左边没有元素的时候，右边用INF_MIN，左边用INF_MAX示意左右的元素：
下图给出具体做的 partition 解题的例子步骤，
这个算法关键在于：
- 要 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)
关键点剖析
- 有序数组容易想到二分查找
- 对小的数组进行二分可升高工夫复杂度
- 依据 leftp1,rightp2,leftp2 和 rightp1 的大小关系确定完结点和膨胀方向
代码
代码反对：JS，CPP， Python3，
JS Code:
/** * 二分解法 * @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]; 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; } }};Java Code:
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 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; }}CPP Code:
class Solution {public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { if (nums1.size() > nums2.size()) swap(nums1, nums2); int M = nums1.size(), N = nums2.size(), L = 0, R = M, K = (M + N + 1) / 2; while (true) { int i = (L + R) / 2, j = K - i; if (i < M && nums2[j - 1] > nums1[i]) L = i + 1; else if (i > L && nums1[i - 1] > nums2[j]) R = i - 1; else { int maxLeft = max(i ? nums1[i - 1] : INT_MIN, j ? nums2[j - 1] : INT_MIN); if ((M + N) % 2) return maxLeft; int minRight = min(i == M ? INT_MAX : nums1[i], j == N ? INT_MAX : nums2[j]); return (maxLeft + minRight) / 2.0; } } }};Python3 Code:
class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: N = len(nums1) M = len(nums2) if N > M: return self.findMedianSortedArrays(nums2, nums1) lo = 0 hi = N combined = N + M while lo <= hi: mid1 = lo + hi >> 1 mid2 = ((combined + 1) >> 1) - mid1 leftp1 = -float("inf") if mid1 == 0 else nums1[mid1 - 1] rightp1 = float("inf") if mid1 == N else nums1[mid1] leftp2 = -float("inf") if mid2 == 0 else nums2[mid2 - 1] rightp2 = float("inf") if mid2 == M else nums2[mid2] # Check if the partition is valid for the case of if leftp1 <= rightp2 and leftp2 <= rightp1: if combined % 2 == 0: return (max(leftp1, leftp2)+min(rightp1, rightp2)) / 2.0 return max(leftp1, leftp2) else: if leftp1 > rightp2: hi = mid1 - 1 else: lo = mid1 + 1 return -1复杂度剖析
- 工夫复杂度：$O(log(min(m, n)))$
- 空间复杂度：$O(log(min(m, n)))$
大家对此有何认识，欢送给我留言，我有工夫都会一一查看答复。更多算法套路能够拜访我的 LeetCode 题解仓库：https://github.com/azl3979858... 。 目前曾经 40K star 啦。
大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。