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)

4 - Median of Two Sorted Arrays

4. Median of Two Sorted Arrays

Level

Description

Solution

Pitfalls

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

4. Median of Two Sorted Arrays

Level

Description

Solution

Pitfalls

Code

All Problems

All Solutions