Hello, I’m Coding Bear. Today is the fourth day of LeetCode’s daily question “Finding the median of two Ordinal groups”.

The question

Given two positively ordered (from small to large) arrays nums1 and nums2 of size m and n, respectively. Find and return the median of these two ordinal groups.

The sample

Input: nums1 = [1,3], nums2 = [2] output: 2.00000 explanation: merge array = [1,2,3], median 2Copy the code

Answer key

Methods a

The easiest way to think about it, because the arrays are ordered, is to merge the two arrays, and then go straight to the median, and do that in O(m+n)O(m+n)O(m+n) O(m+n). But obviously we don’t need to merge the two arrays, because the arrays are ordered. We can just set two Pointers to the heads of the two arrays and compare them until we find the median, which takes O(m+n2)O(\frac{m+n}{2})O(2m+n).

Time complexity: O(m+n)O(m+n)O(m+n)

Space complexity: O(m+n)O(m+n)O(m+n)

Method 2

In this case, if m+n is odd, then the median is the number that is less than (m+n+1)/2 in both arrays; If m+n is even, then the median is the average of (m+n)/2 and (m+n)/2+1 of the two arrays, so the general case of the problem can be translated to finding the KTH smallest number of two ordered arrays.

Because the array is ordered, and the position to find (median) is determined, we can use the binary algorithm to speed up the search for the KTH smallest number of the two ordered arrays, and take the KTH / 2nd smallest number of the two arrays, If nums1 [1] k2 – or less num2 \ [k2-1] text {nums1} [\ frac {k} {2} – 1] \ le \ text {num2} [\ frac {k} {2} – 1] nums1 num2 or less [2 k – 1] [2 k – 1), Then the first k/2 number of nums1 must not be the KTH smallest number, so it can be discarded directly, then k can be subtracted from k/2, And continue the nums1 \ [1, k2 – m – 1] text {nums1} [\ frac {k}, {2} – 1 m – 1] nums1 [k – 1, 2 m – 1) and nums2 \ [0, n – 1] text {nums2} [0, 1 n -] nums2 [0, 1 n -] in the first K / 2 small number, whereas nums1 [1] k2 – > num2 \ [k2-1] text {nums1} [\ frac {k} {2} – 1] > \ text {num2} [\ frac {k} {2} – 1] nums1 [2 k – 1] > num2 [2 k – 1), You can also discard the first k/2 number of NUMs2. In the same way that k goes to K over 2, you can change k over 2 to k over 4….. 1, k=1 returns the first smaller number in both arrays.

Points to note:

  • How to
    nums1 \text{nums1}     或
    nums2 \text{nums2}     The remaining number is less thank/2One, then take the last number at the end.
  • if
    nums1 \text{nums1}     或
    nums2 \text{nums2}     Null, indicating that all elements in the array are excluded and can be returned directly from another arraykSmall elements.

Time complexity: O(log⁡(n+m))O(\log(n+m))O(log(n+m))

Space complexity: O(n+m)O(n+m)O(n+m)

Summary of knowledge points: binary algorithm

C + + code

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(),  n = nums2.size(a);if ((m + n) & 1)
            return getKthNum(nums1, nums2, (m + n + 1) / 2);
        else
            return (getKthNum(nums1, nums2, (m + n) / 2) +
                    getKthNum(nums1, nums2, (m + n) / 2 + 1)) / 2.0;
    }

    int getKthNum(vector<int>& nums1, vector<int>& nums2, int k) {
        int m1 = 0, m2 = nums1.size(), n1 = 0, n2 = nums2.size(a);while(true) {
            if (m1 == m2)
                return nums2[n1 + k - 1];
            if (n1 == n2)
                return nums1[m1 + k - 1];
            if (k == 1)
                return min(nums1[m1], nums2[n1]);

            int mNextIndex = min(m1 + k / 2 - 1, m2 - 1);
            int nNextIndex = min(n1 + k / 2 - 1, n2 - 1);
            if (nums1[mNextIndex] <= nums2[nNextIndex]) {
                k -= mNextIndex - m1 + 1;
                m1 = mNextIndex + 1;
            } else {
                k -= nNextIndex - n1 + 1;
                n1 = nNextIndex + 1; }}}};Copy the code

Java code

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length,  n = nums2.length;
        if ((m + n)  % 2= =1)
            return getKthNum(nums1, nums2, (m + n + 1) / 2);
        else
            return (getKthNum(nums1, nums2, (m + n) / 2) +
                getKthNum(nums1, nums2, (m + n) / 2 + 1)) / 2.0;
    }
    int getKthNum(int[] nums1, int[] nums2, int k) {
        int m1 = 0, m2 = nums1.length, n1 = 0, n2 = nums2.length;
        while(true) {
            if (m1 == m2)
                return nums2[n1 + k - 1];
            if (n1 == n2)
                return nums1[m1 + k - 1];
            if (k == 1)
                return Math.min(nums1[m1], nums2[n1]);

            int mNextIndex = Math.min(m1 + k / 2 - 1, m2 - 1);
            int nNextIndex = Math.min(n1 + k / 2 - 1, n2 - 1);

            if (nums1[mNextIndex] <= nums2[nNextIndex]) {
                k -= mNextIndex - m1 + 1;
                m1 = mNextIndex + 1;
            } else {
                k -= nNextIndex - n1 + 1;
                n1 = nNextIndex + 1; }}}}Copy the code

Title link: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

I am a programming bear, continue to output LeetCode problems, dafang interview, dafang reliable point to point to push related content, focus on “a programming bear”, get information!

Welcome to “follow”, “like”, “retweet” support ~