Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/4.html
4. Median of Two Sorted Arrays
Level
Hard
Description
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
Solution
Use the idea of binary search. First of all, if nums1.length > nums2.length
, then swap the two arrays nums1
and nums2
.
Next, search in the shorter array nums1
to make the algorithm more efficient. Initially let low
be 0 and high
be nums1.length
. Each time set index1 = (high - low) / 2 + low
, and let index2 = (nums1.length + nums2.length + 1) / 2 - index1
. If nums1[index1] < nums2[index2 - 1]
, then set low = index1 + 1
. If nums1[index1 - 1] > nums2[index2]
, then set high = index1 - 1
. Otherwise, if the sum of the two arrays’ lengths is odd, then the median is either nums1[index1 - 1]
or nums2[index2 - 1]
. If the sum of the two arrays’ lengths is even, then the other element that determines the median is either nums1[index1]
or nums[index2]
. Calculate the median accordingly.
Why is it ““target/2”” ??? For example, [1,3,5,…,99], [2,4,6,…,100] two cases
- A total of 100 numbers, then the 50th in all sorts. The average number from the two arrays is 25 numbers each
- If it is not average, then [1,2,3,…,50], [51,52,…,100] are all taken from the first array, that is, the first 25 must be From the first array
case m is much longer than n midIndex/2 to check private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
Pitfalls
- The k in dfs is the number of several, not the index. But start/end is index
- leftMedian and rightMedian are also numbers, not index
int leftMedian = (m + n + 1) / 2;
int rightMedian = (m + n + 2) / 2;
- dfs termination condition
k==1
if (k == 1) { return Math.min(nums1[start1], nums2[start2]); }
solution-2: The optimal solution O(log min(m,n))
, a short array of binary search
Code
-
public class Median_of_Two_Sorted_Arrays { // time: O(log(m,n)) // space: O(1) class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int leftMedian = (n + m + 1) / 2; int rightMedian = (n + m + 2) / 2; return (getKth(nums1, 0, m - 1, nums2, 0, n - 1, leftMedian) + getKth(nums1, 0, m - 1, nums2, 0, n - 1, rightMedian)) * 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; 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)); } } } // good ref, with no array copy // https://www.geeksforgeeks.org/median-two-sorted-arrays-different-sizes-ologminn-m/ // ref: https://leetcode.com/articles/median-of-two-sorted-arrays/ /* Time complexity: O(log(min(m,n))). At first, the searching range is [0, m]. And the length of this searching range will be reduced by half after each loop. So, we only need log(m) loops. Since we do constant operations in each loop, so the time complexity is O(log(m)). Since m <= nm≤n, so the time complexity is O(log(min(m,n))). Space complexity: O(1)O(1). We only need constant memory to store 99 local variables, so the space complexity is O(1). */ // time: O(log min(m,n)) // space: O(1) class Solution_iteration { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int length1 = nums1.length, length2 = nums2.length; if (length1 > length2) { int[] tempArray = nums1; nums1 = nums2; nums2 = tempArray; int temp = length1; length1 = length2; length2 = temp; } int low = 0, high = length1, halfLength = (length1 + length2 + 1) / 2; while (low <= high) { int index1 = (high - low) / 2 + low; int index2 = halfLength - index1; if (index1 < high && nums1[index1] < nums2[index2 - 1]) low = index1 + 1; else if (index1 > low && nums1[index1 - 1] > nums2[index2]) high = index1 - 1; else { int maxLeft = index1 == 0 ? nums2[index2 - 1] : index2 == 0 ? nums1[index1 - 1] : Math.max(nums1[index1 - 1], nums2[index2 - 1]); if ((length1 + length2) % 2 == 1) return maxLeft; int minRight = index1 == length1 ? nums2[index2] : index2 == length2 ? nums1[index1] : Math.min(nums1[index1], nums2[index2]); return (maxLeft + minRight) / 2.0; } } return 0.0; } } public class Solution2_bruteForce { public double findMedianSortedArrays(int[] nums1, int[] nums2) { if(nums1 == null || nums2 == null) { return -10000; } int totalLength = nums1.length + nums2.length; int mid = totalLength / 2; if (totalLength % 2 == 1) { return findTarget(nums1, nums2, mid); } else { return (findTarget(nums1, nums2, mid) + findTarget(nums1, nums2, mid - 1)) / 2; } } // brute force, counting. O(m+n) public double findTarget(int[] nums1, int[] nums2, int targetIndex) { int p1 = 0; int p2 = 0; while(p1 < nums1.length || p2 < nums2.length) { if(p1 + p2 == targetIndex) { int v1updated = p1 < nums1.length ? nums1[p1] : Integer.MAX_VALUE; int v2updated = p2 < nums2.length ? nums2[p2] : Integer.MAX_VALUE; return Math.min(v1updated, v2updated); } int v1 = p1 < nums1.length ? nums1[p1] : Integer.MAX_VALUE; int v2 = p2 < nums2.length ? nums2[p2] : Integer.MAX_VALUE; if(v1 < v2) { p1++; } else { p2++; } } return -10000; // or throw exception "result not found" } } } ############ class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int left = (m + n + 1) / 2; int right = (m + n + 2) / 2; return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0; } private int findKth(int[] nums1, int i, int[] nums2, int j, int k) { if (i >= nums1.length) { return nums2[j + k - 1]; } if (j >= nums2.length) { return nums1[i + k - 1]; } if (k == 1) { return Math.min(nums1[i], nums2[j]); } int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE; int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE; if (midVal1 < midVal2) { return findKth(nums1, i + k / 2, nums2, j, k - k / 2); } return findKth(nums1, i, nums2, j + k / 2, k - k / 2); } }
-
// OJ: https://leetcode.com/problems/median-of-two-sorted-arrays/ // Time: O(log(min(M, N))) // Space: O(1) // Ref: https://leetcode.com/problems/median-of-two-sorted-arrays/solution/ // Ref: https://youtu.be/LPFhl65R7ww 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; } } } };
-
class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: def findKth(i: int, j: int, k: int) -> float: if i >= m: return nums2[j + k - 1] if j >= n: return nums1[i + k - 1] if k == 1: return min(nums1[i], nums2[j]) # Division a // b : floordiv(a, b) midVal1 = nums1[i + k // 2 - 1] if i + k // 2 - 1 < m else math.inf midVal2 = nums2[j + k // 2 - 1] if j + k // 2 - 1 < n else math.inf if midVal1 < midVal2: return findKth(i + k // 2, j, k - k // 2) else: return findKth(i, j + k // 2, k - k // 2) m = len(nums1) n = len(nums2) # Division a // b : floordiv(a, b) left = (m + n + 1) // 2 right = (m + n + 2) // 2 return (findKth(0, 0, left) + findKth(0, 0, right)) / 2.0 ############ class Solution(object): def findMedianSortedArrays(self, nums1, nums2): a, b = sorted((nums1, nums2), key=len) m, n = len(a), len(b) after = (m + n - 1) / 2 lo, hi = 0, m while lo < hi: i = (lo + hi) / 2 if after - i - 1 < 0 or a[i] >= b[after - i - 1]: hi = i else: lo = i + 1 i = lo nextfew = sorted(a[i:i + 2] + b[after - i:after - i + 2]) return (nextfew[0] + nextfew[1 - (m + n) % 2]) / 2.0
-
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { m, n := len(nums1), len(nums2) left, right := (m+n+1)/2, (m+n+2)/2 var findKth func(i, j, k int) int findKth = func(i, j, k int) int { if i >= m { return nums2[j+k-1] } if j >= n { return nums1[i+k-1] } if k == 1 { return min(nums1[i], nums2[j]) } midVal1 := math.MaxInt32 midVal2 := math.MaxInt32 if i+k/2-1 < m { midVal1 = nums1[i+k/2-1] } if j+k/2-1 < n { midVal2 = nums2[j+k/2-1] } if midVal1 < midVal2 { return findKth(i+k/2, j, k-k/2) } return findKth(i, j+k/2, k-k/2) } return (float64(findKth(0, 0, left)) + float64(findKth(0, 0, right))) / 2.0 } func min(a, b int) int { if a < b { return a } return b }
-
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} 012345 */ var findMedianSortedArrays = function (nums1, nums2) { if (nums1.length == 0 || nums2.length == 0) { if ((nums1.length + nums2.length) % 2 == 1) { const index = parseInt((nums1.length + nums2.length) / 2); return nums2.length == 0 ? nums1[index] : nums2[index]; } else { let nums = nums2.length == 0 ? nums1 : nums2; const index = nums.length / 2; return (nums[index - 1] + nums[index]) / 2; } } if (nums1.length > nums2.length) { swap(nums1, nums2); } const M = nums1.length, N = nums2.length; let min = 0, max = M, half = parseInt((M + N + 1) / 2); // 连个数组合并的中间值 while (min <= max) { let i = parseInt((min + max) / 2); // nums1 的索引值 let j = half - i; // num2 的索引值 if (i < max && nums2[j - 1] > nums1[i]) { min++; } else if (i > min && nums1[i - 1] > nums2[j]) { max--; } else { let maxLeft = 0; if (i == 0) { maxLeft = nums2[j - 1]; } else if (j == 0) { maxLeft = nums1[i - 1]; } else { maxLeft = Math.max(nums1[i - 1], nums2[j - 1]); } if ((M + N) % 2 == 1) { return maxLeft; } let minRight = 0; if (i == M) { minRight = nums2[j]; } else if (j == N) { minRight = nums1[i]; } else { minRight = Math.min(nums1[i], nums2[j]); } return (maxLeft + minRight) / 2; } } return 0; }; function swap(a, b) { let tmp = a; a = b; b = tmp; } const nums1 = [4, 5]; const nums2 = [1, 2, 3]; findMedianSortedArrays(nums1, nums2); /** * 实现思路 * 先排除空数组的情况 * 数组从小到大排序 * 取小数组的中间值 * 取大数组的索引 = 总中间值-小数组中间值 * 循环直到符合条件 * 如果都不符合条件,那么说明中间值在两个数组的左边或者右边 */
-
using System; using System.Linq; class Range { public static Range Empty = new Range(new int[0], 0, -1); public readonly int[] Numbers; public readonly int LeftIndex; public readonly int RightIndex; public int Count { get { return RightIndex - LeftIndex + 1; } } public int this[int index] { get { if (index >= Count) { throw new IndexOutOfRangeException(); } return Numbers[LeftIndex + index]; } } public Range(int[] numbers) : this(numbers, 0, numbers.Length - 1) { } public Range(int[] numbers, int leftIndex, int rightIndex) { Numbers = numbers; LeftIndex = leftIndex; RightIndex = rightIndex; if (RightIndex < LeftIndex) RightIndex = LeftIndex - 1; } public Range GetSubRange(int lowerBound, int upperBound) { if (lowerBound > upperBound) return Empty; var leftIndex = lowerBound == int.MinValue ? LeftIndex : Search(lowerBound); var rightIndex = upperBound == int.MaxValue ? RightIndex : Search(upperBound + 1) - 1; return new Range(Numbers, leftIndex, rightIndex); } private int Search(int target) { var l = 0; var r = Numbers.Length - 1; while (l < r) { var mid = (l + r) / 2; if (Numbers[mid] < target) { l = mid + 1; } else { r = mid; } } return Numbers[l] >= target ? l : l + 1; } } public class Solution { public double FindMedianSortedArrays(int[] nums1, int[] nums2) { var totalNumbers = nums1.Length + nums2.Length; var targetOrder1 = (totalNumbers + 1)/2; var targetOrder2 = (totalNumbers + 2)/2; var range1 = new Range(nums1); var range2 = new Range(nums2); var number1 = FindMedianSortedArrays(range1, range2, targetOrder1); var number2 = targetOrder1 == targetOrder2 ? number1 : FindMedianSortedArrays(range1, range2, targetOrder2); return ((double) number1 + number2)/2; } private int FindMedianSortedArrays(Range range1, Range range2, int targetOrder) { if (range1.Count == 0) { return range2[targetOrder - 1]; } if (range2.Count == 0) { return range1[targetOrder - 1]; } var midNumber = range1[(range1.Count - 1)/2]; var midRanges = new[] { range1.GetSubRange(midNumber, midNumber), range2.GetSubRange(midNumber, midNumber) }; var leftRanges = new[] { new Range(range1.Numbers, range1.LeftIndex, midRanges[0].LeftIndex - 1), new Range(range2.Numbers, range2.LeftIndex, midRanges[1].LeftIndex - 1) }; var rightRanges = new[] { new Range(range1.Numbers, midRanges[0].RightIndex + 1, range1.RightIndex), new Range(range2.Numbers, midRanges[1].RightIndex + 1, range2.RightIndex) }; var leftCount = leftRanges.Sum(r => r.Count); var midCount = midRanges.Sum(r => r.Count); var rightCount = rightRanges.Sum(r => r.Count); if (leftCount == 0 && rightCount == 0) { return midNumber; } if (leftCount >= targetOrder) { return FindMedianSortedArrays(leftRanges[0], leftRanges[1], targetOrder); } if (leftCount + midCount >= targetOrder) { return FindMedianSortedArrays(midRanges[0], midRanges[1], targetOrder - leftCount); } return FindMedianSortedArrays(rightRanges[0], rightRanges[1], targetOrder - leftCount - midCount); } }
-
import std/[algorithm, sequtils] proc medianOfTwoSortedArrays(nums1: seq[int], nums2: seq[int]): float = var fullList: seq[int] = concat(nums1, nums2) value: int = fullList.len div 2 fullList.sort() if fullList.len mod 2 == 0: result = (fullList[value - 1] + fullList[value]) / 2 else: result = fullList[value].toFloat() # Driver Code # var # arrA: seq[int] = @[1, 2] # arrB: seq[int] = @[3, 4, 5] # echo medianOfTwoSortedArrays(arrA, arrB)