Leetcode (4) -- find the median of two positively ordered arrays

Leetcode（4）—— Find the median of two positive arrays

subject

Given two sizes, they are $m$ and $n$ Positive order of （ From small to large ） Array $nums1$ and $nums2$. Please find and return the values of these two positive ordered arrays Median .

The time complexity of the algorithm should be $O(log(m+n))$.

Example 1：

Input ：nums1 = [1,3], nums2 = [2]
Output ：2.00000
explain ： Merge array = [1,2,3] , Median 2

Example 2：

Input ：nums1 = [1,2], nums2 = [3,4]
Output ：2.50000
explain ： Merge array = [1,2,3,4] , Median (2 + 3) / 2 = 2.5

Tips ：

• nums1.length == m
• nums2.length == n
• $0$ <= m <= $1000$
• $0$ <= n <= $1000$
• $1$ <= m + n <= $2000$
• $-10^6$ <= nums1[i], nums2[i] <= $10^6$

Answer key

Other methods such as merging and searching will not be written , The time complexity is not up to the requirements and simple

​​   Use merge mode , Merge two ordered arrays , Get a large ordered array . The element in the middle of a large ordered array , Is the median .

• There is no need to merge two ordered arrays , Just find the position of the median . Since the length of the two arrays is known , Therefore, the sum of the subscripts of the two arrays corresponding to the median is also known . Maintain two pointers , Initially, it points to the subscripts of two arrays $0$ The location of , Move the pointer to the smaller value back one bit at a time （ If a pointer has reached the end of the array , Then you just need to move the pointer of another array ）, Until you reach the median .
• Suppose that the lengths of two ordered arrays are $m$ and $n$, How complex are the above two ideas ？

​​   The time complexity of the first idea is $O(m+n)$, The space complexity is $O(m+n)$. Although the second idea can reduce the spatial complexity to $O(1)$, But the time complexity is still $O(m+n)$.

Method 1 ： Two points search

Ideas

​​   If time complexity is required $\log$, It's usually a binary search , This problem can also be realized by binary search .

​​   According to the definition of the median , When $m+n$ It's an odd number , The median is the... Of two ordered arrays $(m+n+1)/2$ Elements , When $m+n$ When it's even , The median is the... Of two ordered arrays $(m+n)/2$ Elements and number $(m+n)/2+1$ The average of the elements .
​​   therefore , This problem can be transformed into ： Find the... In two ordered arrays $k$ Small number , When $m+n$ It's an odd number ,$k$ by $(m+n)/2+1$, When $m+n$ When it's even ,$k$ by $(m+n)/2$ and $(m+n)/2+1$.

The specific algorithm is as follows ：

​​   Suppose two ordered arrays are $\text{A}$ and $\text{B}$. To find number one $k$ Elements , We can compare $\text{A}[k/2-1]$ and $\text{B}[k/2-1]$, among $/$ Represents integer division .
​​   because $\text{A}[k/2-1]$ and $\text{B}[k/2-1]$ Of front There were $\text{A}[0..k/2-2]$ and $\text{B}[0..k/2-2]$, namely $k/2-1$ Elements , about $\text{A}[k/2-1]$ and $\text{B}[k/2-1]$ The smaller of , At most, there will only be $(k/2-1)+(k/2-1)\le k-2$ It's smaller than that , Then it can't be the first $k$ Small number .

So we Three situations can be summed up ：

• If $\text{A}[k/2-1]<\text{B}[k/2-1]$, More than $\text{A}[k/2-1]$ The number that is small or equal to is only $\text{A}$ Before $k/2-1$ Sum of numbers $\text{B}$ Before $k/2-1$ Number , I.e. ratio $\text{A}[k/2-1]$ Small number most Only $k-2$ individual , therefore $\text{A}[k/2-1]$ It can't be number one $k$ Number ,$\text{A}[0]$ To $\text{A}[k/2-1]$ It can't be the first $k$ Number ,$\text{A}[0]$ To $\text{A}[k/2-1]$ You can exclude everything .
• If $\text{A}[k/2-1]>\text{B}[k/2-1]$, be Can be ruled out $\text{B}[0]$ To $\text{B}[k/2-1]$.
• If $\text{A}[k/2-1]=\text{B}[k/2-1]$, be It can be classified into the first case .

You can see , Compare $\text{A}[k/2-1]$ and $\text{B}[k/2-1]$ after , Can be ruled out $k/2$ The first can't be the first $k$ Small number , The search scope is reduced by half . meanwhile , We The binary search will continue on the excluded new array , And according to the number of excluded numbers , Reduce $k$ Value , This is because none of the numbers we exclude is greater than $k$ Small number .

There are three situations that need special treatment ：

• If $\text{A}[k/2-1]$ perhaps $\text{B}[k/2-1]$ Transboundary , Then we can select the last element in the corresponding array . under these circumstances , We have to reduce... According to the number of exclusions $k$ Value , Instead of directly $k$ subtract $k/2$.
• If an array is empty , Indicates that all elements in the array are excluded , We can directly return the... In another array $k$ Small elements .
• If $k=1$, We just need to return the minimum value of the first element of two arrays .

Example

An example is given to illustrate the above algorithm . Suppose two ordered arrays are as follows ：

The lengths of the two ordered arrays are $4$ and $9$, The sum of the lengths is $13$, The median is the... Of two ordered arrays $7$ Elements , So we need to find the second $k=7$ Elements .

Compare two ordered arrays with the subscript $k/2-1=2$ Number of numbers , namely $\text{A}[2]$ and $\text{B}[2]$, This is shown below ：

because $\text{A}[2]>\text{B}[2]$, Thus eliminate $\text{B}[0]$ To $\text{B}[2]$, It's an array $\text{B}$ Subscript offset （offset） Turn into $3$, Simultaneous updating $k$ Value ：$k=k-k/2=4$.

The next step is to find , Compare two ordered arrays with the subscript $k/2-1=1$ Number of numbers , namely $\text{A}[1]$ and $\text{B}[4]$, This is shown below , The square brackets indicate the number that has been excluded .

because $\text{A}[1]<\text{B}[4]$, Thus eliminate $\text{A}[0]$ To $\text{A}[1]$, It's an array $\text{A}$ The subscript offset of becomes $2$, Simultaneous updating $k$ Value ：$k=k-k/2=2$.

The next step is to find , Compare two ordered arrays with the subscript $k/2-1=0$ Number of numbers , Comparison $\text{A}[2]$ and $\text{B}[3]$, This is shown below , The square brackets indicate the number that has been excluded .

because $\text{A}[2]=\text{B}[3]$, According to the previous rules , exclude $\text{A}$ The elements in , Thus eliminate $\text{A}[2]$, It's an array $\text{A}$ The subscript offset of becomes $3$, Simultaneous updating $k$ Value ： $k=k-k/2=1$.

because $k$ The value of the into $1$, So compare the first number in the range of non excluded subscripts in two ordered arrays , The smaller number is the... Th $k$ Number , because $\text{A}[3]>\text{B}[3]$, So the first $k$ The number is $\text{B}[3]=4$.

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
    
        /*  Main idea ： To find number one  k (k>1)  Small elements , Then take it  pivot1 = nums1[k/2-1]  and  pivot2 = nums2[k/2-1]  Compare  *  there  "/"  To divide or divide  * nums1  Less than equal to  pivot1  The elements of  nums1[0 .. k/2-2]  total  k/2-1  individual  * nums2  Less than equal to  pivot2  The elements of  nums2[0 .. k/2-2]  total  k/2-1  individual  *  take  pivot = min(pivot1, pivot2), Less than or equal to... In two arrays  pivot  The total number of elements will not exceed  (k/2-1) + (k/2-1) <= k-2  individual  *  such  pivot  In itself, the biggest can only be the second  k-1  Small elements  *  If  pivot = pivot1, that  nums1[0 .. k/2-1]  It can't be the second  k  Small elements . Take all of these elements  " Delete ", The rest as new  nums1  Array  *  If  pivot = pivot2, that  nums2[0 .. k/2-1]  It can't be the second  k  Small elements . Take all of these elements  " Delete ", The rest as new  nums2  Array  *  Because of us  " Delete "  Some elements were added （ These elements are better than  k  Small elements should be small ）, So it needs to be modified  k  Value , Subtract the number of deletions  */

        int m = nums1.size();
        int n = nums2.size();
        int index1 = 0, index2 = 0;

        while (true) {
    
            //  Boundary situation 
            if (index1 == m)
                return nums2[index2 + k - 1];
            if (index2 == n)
                return nums1[index1 + k - 1];
            if (k == 1)
                return min(nums1[index1], nums2[index2]);

            //  Normal condition 
            int newIndex1 = min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = min(index2 + k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
    
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            } else {
    
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    
        int totalLength = nums1.size() + nums2.size();
        if (totalLength % 2 == 1)
            return getKthElement(nums1, nums2, (totalLength + 1) / 2);
        else
            return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
    }
};

Complexity analysis

Time complexity ：$O(log(m+n))$, among $m$ and $n$ They are arrays ${\text{nums}}_1$ and ${\text{nums}}_2$ The length of . Initially there is $k=(m+n)/2$ or $k=(m+n)/2+1$, Each cycle can reduce the search range by half , So the time complexity is $O(\log (m+n))$.
Spatial complexity ：$O(1)$

Method 2 ： Two points search + Partition array

Ideas

​​   In order to solve this problem by using partition , You need to understand 「 What is the role of the median 」, If you understand the role of median , It's very close to the answer .. In Statistics , The median is used to ：

Divide a set into two subsets of equal length , The elements in one subset are always larger than those in the other .

First , In any position $i$ take $\text{A}$ Divided into two parts ：

because $\text{A}$ There is $m$ Elements , So there is $m+1$ A method of division （$i\in [0,m]$）.

$\text{len}(\text{left\_A})=i,\text{len}(\text{right\_A})=m-i$
Be careful ： When $i=0$ when ,$\text{left\_A}$ For an empty set , And when $i=m$ when , $\text{right\_A}$ For an empty set .

In the same way , In any position $j$ take $\text{B}$ Divided into two parts ：

take $\text{left\_A}$ and $\text{left\_B}$ Put in a collection , And will $\text{right\_A}$ and $\text{right\_B}$ Put into another set . Then name the two new sets $\text{left\_part}$ and $\text{right\_part}$：

When $\text{A}$ and $\text{B}$ When the total length of is even , If you can confirm ：

• $\text{len}(\text{left\_part})=\text{len}(\text{right\_part})$
• $\max (\text{left\_part})\le \min (\text{right\_part})$

that ,$\{\text{A},\text{B}\}$ All elements in have been divided into two parts of the same length , And the elements in the former part are always less than or equal to the elements in the latter part . The median is the average of the maximum value of the former part and the minimum value of the latter part ：
$$\text{median}=\frac{\text{max}(\text{left}\_\text{part})+\text{min}(\text{right}\_\text{part})}{2}$$

When $\text{A}$ and $\text{B}$ When the total length of is odd , If you can confirm ：

• $\text{len}(\text{left\_part})=\text{len}(\text{right\_part})+1$
• $\max (\text{left\_part})\le \min (\text{right\_part})$

that ,$\{\text{A},\text{B}\}$ All elements in have been divided into two parts , The former part has one more element than the latter part , And the elements in the former part are always less than or equal to the elements in the latter part . The median is the maximum of the previous part ：
$$\text{median}=\text{max}(\text{left}\_\text{part})$$

The first condition is different when the total length is even and odd , But you can combine the two situations . The second condition is the same when the total length is even and odd .

Make sure these two conditions , Just make sure that ：

• $i+j=m-i+n-j$（ When $m+n$ For the even ） or $i+j=m-i+n-j+1$（ When $m+n$ It's odd ）. To the left of the equal sign is the number of elements in the previous part , To the right of the equal sign is the number of elements in the latter part . take $i$ and $j$ Move all to the left of the equal sign , We can get it $i+j=\frac{m+n+1}{2}$. The score result here only retains the integer part .
• $0\le i\le m$,$0\le j\le n$. If we stipulate $\text{A}$ Less than or equal to $\text{B}$ The length of , namely $m\le n$. This is for any $i\in [0,m]$, There are $j=\frac{m+n+1}{2}-i\in [0,n]$, So we're in $[0,m]$ Enumeration within the scope of $i$ And get the $j$, There is no need for additional properties .
  • If $\text{A}$ The length of , Then we just exchange $\text{A}$ and $\text{B}$ that will do .
  • If $m>n$, So the conclusion is $j$ It could be negative .
• $\text{B}[j-1]\le \text{A}[i]$ as well as $\text{A}[i-1]\le \text{B}[j]$, That is, the maximum value of the former part is less than or equal to the minimum value of the latter part .

To simplify the analysis , hypothesis $\text{A}[i-1],\text{B}[j-1],\text{A}[i],\text{B}[j]$ There is always . about $i=0$、$i=m$、$j=0$、$j=n$ Such critical conditions , We just need to stipulate $\text{A}[-1]=\text{B}[-1]=-\infty$,$A[m]=\text{B}[n]=\infty$ that will do . This is also more intuitive ： When an array does not appear in the previous part , The corresponding value is negative infinity , It will not affect the maximum value of the previous part ; When an array does not appear in the latter part , The corresponding value is positive infinity , It will not affect the minimum value of the latter part .

So what we need to do is ：

stay $[0,m]$ Find $i$, bring ：
$\text{B}[j-1]\le \text{A}[i]$ And $\text{A}[i-1]\le \text{B}[j]$, among $j=\frac{m+n+1}{2}-i$

We prove that it is equivalent to ：

stay $[0,m]$ Find the biggest in $i$, bring ：
$\text{A}[i-1]\le \text{B}[j]$, among $j=\frac{m+n+1}{2}-i$

This is because ：

• When $i$ from $0\sim m$ When increasing ,$\text{A}[i-1]$ Increasing ,$\text{B}[j]$ Decline , So there must be a biggest $i$ Satisfy $\text{A}[i-1]\le \text{B}[j]$;
• If $i$ It's the biggest , It means that $i+1$ dissatisfaction . take $i+1$ You can get $\text{A}[i]>\text{B}[j-1]$, That is to say $\text{B}[j-1]<\text{A}[i]$, Just before the equivalent transformation with us $i$ The nature of is consistent （ Even better ）.

So we can do something about $i$ stay $[0,m]$ Binary search on the interval of , Find the greatest satisfaction $\text{A}[i-1]\le \text{B}[j]$ Of $i$ value , You get the method of division . here , Divide the maximum value in the previous element , And the minimum value of the elements after division , It can be used as the median of these two arrays .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    
        if (nums1.size() > nums2.size()) {
    
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.size();
        int n = nums2.size();
        int left = 0, right = m;
        // median1： The maximum of the previous part 
        // median2： The minimum of the latter part 
        int median1 = 0, median2 = 0;

        while (left <= right) {
    
            //  The former part contains  nums1[0 .. i-1]  and  nums2[0 .. j-1]
            //  The latter part contains  nums1[i .. m-1]  and  nums2[j .. n-1]
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;

            // nums_im1, nums_i, nums_jm1, nums_j  respectively  nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            int nums_im1 = (i == 0 ? INT_MIN : nums1[i - 1]);
            int nums_i = (i == m ? INT_MAX : nums1[i]);
            int nums_jm1 = (j == 0 ? INT_MIN : nums2[j - 1]);
            int nums_j = (j == n ? INT_MAX : nums2[j]);

            if (nums_im1 <= nums_j) {
    
                median1 = max(nums_im1, nums_jm1);
                median2 = min(nums_i, nums_j);
                left = i + 1;
            } else {
    
                right = i - 1;
            }
        }

        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }
};

Complexity analysis

Time complexity ：$O(\log \min (m,n)))$, among $m$ and $n$ They are arrays ${\text{nums}}_1$ and ${\text{nums}}_2$ The length of . The search interval is $[0,m]$, The length of this interval will be reduced to half of the original after each cycle . therefore , Just execute $\log m$ Secondary cycle . Since the number of operations in each cycle is constant , So the time complexity is $O(\log m)$. Because we may need to exchange ${\text{nums}}_1$ and ${\text{nums}}_2$ bring $m\le n$ And we Only the shorter array is binary searched , So the time complexity is $O(\log \min (m,n)))$.
Spatial complexity ：$O(1)$