Location>code7788 >text

LeetCode Problemset-4 - Finding the median of two ordered arrays, illustrated, six solutions, 10,000 words of explanation

Popularity:579 ℃/2024-09-19 11:29:39

Question : Given two positively ordered (from smallest to largest) arrays nums1 and nums2 of size m and n respectively, find and return the median of these two positively ordered arrays.

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

As the first difficult level topic I have encountered so far, I feel that this question is still quite difficult to study for three days to finally study and understand, the following is to share with you a few solutions to this question, please follow my thinking step by step to solve this question.

Solution I. Entertainment method (built-in method)

In view of the difficulty of this problem, we first come to an entertaining solution to relax a little, and in the project encountered such a demand I think the vast majority of more or less will be dealt with in this way directly, and this idea is more in line with the most intuitive thinking. Simply put the idea is to directly use the language comes with the method of the first two arrays spliced together, and then after the splicing of the array sorting, and finally according to the number of arrays parity directly access to the value. Code is as follows:

//Direct Merge and Sort Arrays Using Built-In Methods
public static double MergedArraySort(int[] nums1, int[] nums2)
{
    var merged = (nums2).ToArray();
    (merged);
    var len = ;
    if (len % 2 == 0)
    {
        return (merged[(len / 2) - 1] + merged[len / 2]) / 2.0;
    }
    else
    {
        return merged[len / 2];
    }
}

Of course we do algorithmic problems to study algorithmic thinking and find better solutions, so we continue to explore more algorithmic solutions.

Solution 2, double pointer + merge array method

Although the above solution has an element of entertainment, it provides the most intuitive idea. We follow the overall idea above and change the call to the language's built-in methods to our own implementation. First, let's sort out the overall idea.

1. First construct a large array that can hold two arrays;

2. Then at the same time from the beginning of the two arrays to start comparing, if the value is smaller then into the large array, the value is larger then continue to compare with the latter elements;

3. Handle the case where array 1 has no data and array 2 has data;

4. Handle the case where array 2 has no data and array 1 has data;

5. Dealing with other situations;

6. So that the two array elements are processed, the array merger is complete, and is ordered;

7. Remove the median according to the number of elements of a large array odd or even.

You can see the actual steps detailed in the picture below:

The realization code is as follows:

//Double Pointer Merged Array after the value method
public static double TwoPointerMergedArray(int[] nums1, int[] nums2)
{
    //create a large array that can hold two arrays
    var list = new int[ + ];
    // index of array1
    var idx1 = 0;
    // index of array 2
    var idx2 = 0; //index of large array
    //Index of large array
    var idx = 0;
    //Exit if both arrays are processed, advancing the index of the large array 1 bit at a time
    while (idx1 < || idx2 < )
    {
        if (idx1 >= )
        {
            //If there is no more data in array 1, advance the index of array 2 by 1 bit after filling it with the current value of array 2
            list[idx] = nums2[idx2++];
        }
        else if (idx2 >= )
        {
            //If there is no more data in array 2, then populate the large array with the current value of array 1, advancing the array 1 index by 1 position
            list[idx] = nums1[idx1++];
        }
        else
        {
            //When both arrays have data, then compare the two current numbers, and the smaller number is populated into the larger array, and its corresponding index is advanced by 1 position.
            if (nums1[idx1] < nums2[idx2])
            {
                list[idx] = nums1[idx1++];
            }
            else
            {
                list[idx] = nums2[idx2++]; } else { list[idx] = nums2[idx2++]; }
            }
        }
        // Large numbers are indexed 1 digit forward
        idx++;
    }
    if (idx % 2 == 0)
    {
        // Even numbers take the middle two digits and average them out
        return (list[(idx / 2) - 1] + list[idx / 2]) / 2.0;
    }
    else
    {
        // for an odd number, take the middle digit and return it directly
        return list[idx / 2]; } else { // for odd numbers, go to the middle digit and return it.
    }
}

Because a large array is constructed the space complexity isO(n+m), since both arrays are traversed once, the time complexity of this algorithm isO(n+m), and therefore cannot satisfy the requirements of the topicO(log(n+m)). Although this solution is not what we are looking for, it does give us a logical basis to continue looking for a better solution.

Solution three, double pointer + direct value method

Thinking about the question, we are asking for the median, and looking back at the solution in the previous section, there is absolutely no need to construct a large array, or to process both arrays, only to find the median, i.e. if by chance we only need to take two values, and if it is an odd number we only need to take one value. Thus there is a great deal of unnecessary computation in the solution of the previous section.

Therefore the entire solution structure of the previous section can be retained by removing the unnecessary ones, the idea is as follows:

1. Simultaneously compare the two arrays from their starting positions and if the value is smaller it is stored in a temporary variable;

2. Handle the case where array 1 has no data and array 2 has data;

3. Handle the case where array 2 has no data and array 1 has data;

4. Dealing with other situations;

5. Reaching the right median position ends the process;

6. Take out the median based on parity and temporary variables.

Let's look at the code first:

//Double Pointer Direct Value Method
public static double TwoPointerDirectValue(int[] nums1, int[] nums2)
{
    //The total length of the two arrays
    var len = + ;
    //left number, even: left median, odd: median of the first one
    var left = 0; //right number, even: left median, odd: first digit of median
    //Right, even: right median, odd: median
    var right = 0; //Array 1 index, even: right median, odd: first digit of median
    // Array 1 index
    var idx1 = 0;; //array 2 index
    // Array 2 index
    var idx2 = 0;; //When the median digit is processed
    //Exit when the median digit has been processed
    while (true)
    {
        //put the previous value first into the left number, and store the current value in the right number
        left = right; if (idx1 >= )
        if (idx1 >= )
        {
            //If there is no more data in array 1, then put the current value of array 2 into the right number and advance the index of array 2 by 1 position
            right = nums2[idx2++];
        }
        else if (idx2 >= )
        {
            // If there is no more data in array 2, then put the current value of array 1 into the right number and advance the index of array 1 by 1 position
            right = nums1[idx1++];
        }
        else
        {
            //When both arrays have data, then compare the two current numbers, put the smaller number into the right number, and advance its corresponding index by 1 position
            if (nums1[idx1] < nums2[idx2])
            {
                right = nums1[idx1++];
            }
            else
            {
                right = nums2[idx2++]; } else { right = nums2[idx2++]; }
            }
        }
        // End processing when the median digit has been processed
        if (len / 2 == idx1 + idx2 - 1)
        {
            break; }
        }
    }
    if (len % 2 == 0)
    {
        // even numbers take the average of the left and right numbers
        return (left + right) / 2.0;
    }
    else
    {
        // for an odd number, return the right number
        return right; } else { // for odd numbers, return the right number.
    }
}

The code reveals several small differences from the previous section's solution as well as key ones.

1. Removed the large array and added two variables, left and right, to store the median;

  1. The key point "left = right;", because we need to store two values to cope with the two cases of parity, so here is a small trick, each iteration before the start of the calculation, the first time the last calculation results stored in the left, and then use the right to store the results of the current calculations, so left, right is two consecutive elements. right are two consecutive elements. If you want to take out the two numbers at the same time in a calculation, obviously the situation will be very complex and difficult to deal with, and this little trick just solves the problem so that you can take out the desired elements in the two calculations.

3. key point why if (len / 2 == idx1 + idx2 - 1) as the end of the processing flag, first of all, why idx1 + idx2 - 1 to be reduced by 1, this is because in the above take the value of the same time are carried out after + + operation, so here to subtract this 1. Then why is len / 2 as the end point, because / is downward rounding, so a chance and even than the odd number of 1, after / 2 after processing the value is the same, and because len is the number of elements of the array, and the number of elements just than the index of the larger 1, so when the array for the odd number of len / 2 on the median, when the array for the even number of len / 2 on the median, so can be regarded as the end of processing mark. Therefore, it can be regarded as the end-of-processing flag.

Because of the removal of building large arrays therefore the space complexity isO(1), since the amount of data to be processed is reduced by half therefore the time complexity isO((n+m)/2), which is the same asO(n+m). So it still doesn't fulfill the requirement.

Solution 4, double pointer + dichotomous exclusion method

Obviously to get to theO(log(n+m)) of the time complexity, it can not be an element by element processing, which can not help but let us think of dichotomous ideas, since one by one processing can not be, then we will deal with a few more at a time, the data do not meet the requirements are excluded, one time to exclude half of this is not closer to our target value is well, and finally arrived at our target value.

We continue to follow the same framework of solution ideas as in the previous section, with some modifications, along the following lines:

1. Simultaneously compare two arrays from halfway between their left median positions and exclude values if they are smaller;

2. Handle the case where array 1 has no data and array 2 has data and end the processing;

3. Handle the case where array 2 has no data and array 1 has data and end the processing;

4. Handle the case where the pointer stays at the left median position and end the processing;

5. After one comparison is complete, continue to take the current position halfway to the left median position for the next comparison;

6. Take out the median based on parity and temporary variables.

Below we have a detailed explanation in conjunction with the illustration.

Finding the left median also means that the left and right medians can be handled directly at the same time.

Let's take a look at the code implementation:

//Double Pointer Binary Exclude lookup method
public static double TwoPointerBinaryExclude(int[] nums1, int[] nums2)
{
    //Total length of the array
    var len = + ;
    // target number, indicates the median in the array of the first number, an even number represents the left median, the odd number represents the median
    var target = (len + 1) / 2; //left median
    // left median
    int left.
    //right median
    int right.
    // Array 1 index
    var idx1 = 0; //array 2 index
    // Array 2 index
    var idx2 = 0;
    //Exit when the median digit has been processed
    while (true)
    {
        //array 1 is out of data, then get the median directly in array 2
        if (idx1 >= )
        {
            //since array 1 is empty, index array 2 forward to the target number
            idx2 += target - 1;
            //Take the median directly
            if (len % 2 == 0)
            {
                //even number
                //left median is the current value
                left = nums2[idx2]; //right median is the next value
                //right median is the next value
                right = nums2[idx2 + 1]; //the right median is the next value
            }
            else
            {
                //Odd numbers with the same left and right medians are the current value
                left = right = nums2[idx2]; } else { // odd number, left and right medians are the current value.
            }
            break; }
        }
        // If there is no data in array 2, then get the median directly in array 1
        if (idx2 >= )
        {
            //Since there is no more data in array 2, index array 1 forward to the target number
            idx1 += target - 1;
            //Take the median directly
            if (len % 2 == 0)
            {
                //even number
                //left median is the current value
                left = nums1[idx1]; //right median is the next value
                //right median is the next value
                right = nums1[idx1 + 1]; //the right median is the next value
            }
            else
            {
                //Odd numbers with the same left and right medians are the current value
                left = right = nums1[idx1]; } else { // odd number, left and right medians are the current value.
            }
            break; }
        }
        //When the target is 1, it means the current value is the value to be found.
        if (target == 1)
        {
            //Take the median directly
            if (len % 2 == 0)
            {
                //even numbers
                if (nums1[idx1] < nums2[idx2])
                {
                    // if nums1 is smaller, see if there are more elements after it
                    if (idx1 + 1 > - 1)
                    {
                        //If there are no elements after it, then the left median is the current value of nums1 and the right median is the current value of nums2
                        left = nums1[idx1].
                        right = nums2[idx2];
                    }
                    else
                    {
                        // If there is an element after it, the left median is the current value of nums1, and the right median is the lesser of the value after the current value of nums1 and the current value of nums2
                        var temp = nums1[idx1 + 1];
                        left = nums1[idx1].
                        right = (nums2[idx2], temp);
                    }
                }
                else
                {
                    // If nums2 is currently small, see if there are elements after it
                    if (idx2 + 1 > - 1)
                    {
                        //If there are no elements after it, then the left median is the current value of nums2 and the right median is the current value of nums1
                        left = nums2[idx2].
                        right = nums1[idx1];
                    }
                    else
                    {
                        // If there is an element after it, the left median is the current value of nums2, and the right median is the lesser of the value after the current value of nums2 and the current value of nums1
                        var temp = nums2[idx2 + 1];
                        left = nums2[idx2].
                        right = (nums1[idx1], temp);
                    }
                }
            }
            else
            {
                // Odd numbers, left and right medians are the same, take the smaller of nums1's current value and nums2's current value.
                left = right = (nums1[idx1], nums2[idx2]);
            }
            break; }
        }
        // Take half of the position of the target
        var half = target / 2;
        // Determine the number nums1 compares to and make sure it's not greater than its own length
        var compare1 = (idx1 + half, ); //determine nums2 to compare with, and make sure it's not bigger than itself.
        // Determine the number of comparisons for nums2 and make sure it's not greater than its own length
        var compare2 = (idx2 + half, ); //compare two arrays of comparisons and make sure they are not larger than themselves.
        //compare two arrays of comparisons, compare-1 because the number of comparisons indicates the first number, minus 1 to the index
        if (nums1[compare1 - 1] < nums2[compare2 - 1]))
        {
            //nums1's compare number is smaller, then exclude it.
            //The number of targets to find needs to be subtracted from the number already excluded
            target -= compare1 - idx1; //while nums1's current number of comparisons is smaller, it is excluded.
            //while nums1 advances to the next excluded element at its current index
            idx1 = compare1; }
        }
        else
        } else
            //nums2's compare number is smaller, then it is excluded
            //The number of targets to be found needs to be subtracted from the number already eliminated
            target -= compare2 - idx2; //while nums2's current index advances to the last excluded element.
            //while nums2 advances to the next excluded element at its current index
            idx2 = compare2; }
        }
    }
    return (left + right) / 2.0; }
}

While the above code is still very much in line with the way we think and understand, there are two issues to think about:

1. Why is it that when two arrays of values are compared the number with the smaller value and the number before it can be directly excluded?

2. All three end-processing marker code blocks contain processing for different cases of parity, making the code lengthy and complex, is there a better way to handle this?

Solution 5, double pointer + bisection to find the Kth decimal method

In this solution, let's answer the two questions above.

In fact, the previous section of the solution already contains a bisection to find the core code of the Kth decimal, because we are in the previous solution to the core is the first to find the left median, so as long as you get the right median to deal with the parity judgment and the relevant code to delete, in fact, to get a bisection to find the Kth decimal algorithm, and then respectively, the left Kth decimal and the right Kth decimal respectively, into the algorithm to get the left median and right median, and finally average to get the median, and finally average to get the median, and finally average to get the median. Finally, the average median.

The specific code is as follows:

//Double Pointer Binary FindKth method
public static double TwoPointerBinaryFindKth(int[] nums1, int[] nums2)
{
    //Left Kth decimal, when even, represents the left median, when odd, represents the median
    var leftKth = ( + + 1) / 2; //rightKth, when even, represents the left median, when odd, represents the middle.
    // the right Kth decimal, when even, represents the right median, when odd, represents the median (because of the / downward rounding feature)
    var rightKth = ( + + 2) / 2; //get the left median, when even, represents the right median, when odd, represents the median (because / downward rounding properties)
    // Get the left median
    var left = TwoPointerBinaryFindKth(leftKth, nums1, nums2);
    // Get the right median
    var rigth = TwoPointerBinaryFindKth(rightKth, nums1, nums2);; //get the right median.
    return (left + rigth) / 2.0;
}
// TwoPointerBinaryFindKth
public static int TwoPointerBinaryFindKth(int kth, int[] nums1, int[] nums2)
{
    // index of array 1
    var idx1 = 0;
    // Array 2 index
    var idx2 = 0;
    //Exit when the Kth decimal is found
    while (true)
    {
        // if array 1 is empty, look for K directly in array 2
        if (idx1 >= )
        {
            // Because array 1 is empty, index 2 forward to the K index.
            idx2 += kth - 1;
            return nums2[idx2].
        }
        // If there is no data in array 2, then look up K directly in array 1
        if (idx2 >= )
        {
            // Since array 2 has no data, index array 1 forward to the index of the number K
            idx1 += kth - 1;
            return nums1[idx1];
        }
        //When the kth decimal is 1, it indicates that the current value is the value to be found
        if (kth == 1)
        {
            return (nums1[idx1], nums2[idx2]);
        }
        // Take out half of the kth decimal place
        var half = kth / 2;
        // Determine the nums1 comparison number and make sure it's not greater than its own length
        var compare1 = (idx1 + half, ); //determine the nums2 comparison number and make sure it's not greater than itself.
        // Determine the number of comparisons for nums2 and make sure it's not greater than its own length
        var compare2 = (idx2 + half, ); //compare two arrays of comparisons and make sure they are not larger than themselves.
        //compare two arrays of comparisons, compare-1 because the number of comparisons indicates the first number, minus 1 to the index
        if (nums1[compare1 - 1] < nums2[compare2 - 1]))
        {
            //nums1's comparison number is smaller, then exclude it
            // the kth decimal number to find needs to be subtracted from the number already excluded
            kth -= compare1 - idx1; //meanwhile nums1 current number of comparisons is excluded.
            //while nums1 current index advances to the next excluded element
            idx1 = compare1.
        }
        else
        {
            //nums2's compare is smaller, then it is excluded.
            //The kth decimal number to find needs to be subtracted from the number already excluded
            kth -= compare2 - idx2.
            //while nums2 advances to the next excluded element at its current index
            idx2 = compare2.
        }
    }
}

Through the code can be found in this solution has solved the second problem in the previous section, through the parity of the two cases around the median is the first digit of the representation of the unification of the need to determine the parity of the problem of different processing logic, at the same time, because of only one number of concern K, so the entire code is concise and clear.

Comparison can also be found in the two solutions to the core of the dichotomous idea part of the code is exactly the same, the difference is that one time to deal with a value and one time to deal with the difference between the two values.

There is also the same question here as in the first question of the previous solution, why is it that when two array values are compared the number with the smaller value and the number before it can be eliminated directly?

We'll explain in more detail the principles that can be ruled out directly here.

First, sort out the ideas, why can be directly excluded? If I can prove that each time the number of elimination are again K small left side of the elimination is not established, so the above problem can be converted to prove that each time the number of elimination are in the K small number of the left side. We keep eliminating numbers from the left side, so the left side keeps changing, but the number on the right side stays the same, so let's switch the problem around and prove that the number of numbers on the right side of the eliminated numbers is greater than or equal to (n-k+1).

Below we take the first exclusion of the following two arrays as an example to do a detailed proof, and the other sub-exclusion of the same reason.

nums1:[1,4,8,9,11]

nums2:[2,3,5,6,7,10]

Since the total number of two arrays is 11, we look for the 6th decimal, i.e., k is 6. Therefore, the first comparison starts from the 6th/2=3th number, i.e., comparing num1[idx2] with num2[idx2]. As shown below.

Since num1[idx2] > num2[idx2], [2,3,5] needs to be eliminated, so prove that the number in the red box must be greater than or equal to (n-k+1=11-6+1=6).

First look at the array nums1 because 8>5 so 8 is definitely left behind, so nums1 has at least (len1-idx2) number of digits greater than 5. Then look at the array num2 because 5 is going to be excluded, so num2 has (len2-(idx2+1)) number of digits greater than 5.

Thus there are at least as many numbers greater than 5 as [(len1-idx2) + (len2-(idx2+1))]

And because idx2 = k/2

So the number of numbers greater than 5 is at least [(len1-k/2)+(len2-(k/2+1))]

Simplifying gives [len1+len2-k+1]

i.e. [n-k+1]

Similarly, if the array for the even number can also be proved, so in order to be able to prove that the number of rows each time the right side of the number of numbers are left greater than or equal to (n - k + 1) number, so it is proved that the number of excluded must be the left side of the first K decimals can be excluded directly, and from the above figure can be found in the exclusion of the number of numbers does not necessarily be the order of the number of, but it does not matter, only in the left side of the first K decimals can be deleted.

Solution 6, double pointer + bisecting to find the equalization method

The two dichotomous solutions above already satisfy the requirements of the question, but there are even better solutions to this problem, so let's continue to explore them.

First think about what properties the median has and whether we can use the properties of the median itself to solve the problem.

The median, also known as the middle value, is the value in the middle of a set of data arranged in order, from which we can derive two properties:

1. If the median is the dividing line, then the number of data on the left and right sides of the median is equal;

2. If the median is the dividing line, then the largest number to the left of the median is necessarily less than or equal to the smallest number to the right of the median.

So how do you apply these two properties to solve a problem?

As shown above, that is, if we find a line to split the two arrays, at the same time to split the line shall prevail, the left part of the split line as a whole as the median of the left part of the split line as a whole as the median of the right part of the split line as a whole as the median of the right part of the right part of the left and right parts of the left and right parts of the line to meet the above two characteristics means that the problem is solved, the topic is transformed into a solution for the line of the split line.

Obviously the above figure is impossible to satisfy because the array is always odd, so no matter how to split the left side and the right side of the number can not be comparable, unless the split line is drawn on a number to divide a number in half, which is obviously impossible, and this can not satisfy the first property.

If you have a problem, solve it. Since we can't make the left and right sides equal for odd-numbered problems, we can always make one side always have one more number than the other side, because of the ordering property, so such a change doesn't affect the second property, which is equivalent to satisfying both properties.

By this point the central frame of mind for solving the problem is in place: find a line that divides the two arrays such that it satisfies, directly or indirectly, the two properties of the median.

With the core ideological framework in place, the next step is to populate the key logical processing points.

First question: where to start the process?

Of course we need to continue with the dichotomy idea, so start the process from the middle of array 1.

Second question: since positional processing starts in the middle of array 1, what about array 2? How do we get the values?

And when the current index of array 1, idx1, is determined, the current index of array 2, idx2, can be calculated from idx1.

Because when the total length of the array is even, the number of left and right sides is equal, we can get

idx1 + idx2 = len1 - idx1 + len2 - idx2,i.e. idx2 = (len1 + len2)/2 - i;

When the total length of the array is computed, we set the left side to be one more number than the right side, which gives us

idx1 + idx2 = len1 - idx1 + len2 - idx2 + 1,i.e. idx2 = (len1 + len2 + 1)/2 - i;

Third question: since the split line is to find out that, and from the middle of the array 1 to start processing, then how should I determine to find in that direction?

You can determine which direction to look in by comparing the maximum value on the left and the minimum value on the right after the split, that is, to do the forward direction you can split the smaller value to the left and the larger value to the right.

Fourth question: what is the rhythm of processing?

The first question also says that since we're still continuing to use the dichotomy idea, each process will take half of the last one.

Fifth question: any other points to note?

The rest is a matter of handling special boundaries, such as splitting to the ends of the array, and a separate section on the parity of the total number of arrays.

Here the whole idea of solving the problem is sorted out completed, the main combing of the core idea framework and key logic processing points, and not specifically to say what are the characteristics of the boundary problems, how to determine the direction of travel, etc., because I feel that the core idea framework + key logic processing points is the most important, and then we assist some illustrations, and then finally look at the source code, basically, a look to understand.

Here's an example of a complete lookup of two arrays applying bisection to find the equalizer.

The specific code is as follows:

//Double Pointer Binary Finding Equalization
public static double TwoPointerBinaryHalves(int[] nums1, int[] nums2)
{
    //When the length of array 1 is greater than the length of array 2, then swap the two arrays to ensure that array 1 is the shorter array
    if ( > )
    {
        // Swap the values of the two variables, C# 7.0 tuple deconstruct assignment syntax
        (nums1, nums2) = (nums2, nums1);
    }
    // left pointer
    int idxLeft = 0;
    //Right pointer
    int idxRight = ;
    // bisecting array 1
    while (idxLeft <= idxRight)
    {
        //calculate the current index of array 1 after bisection
        var idx1 = (idxLeft + idxRight) / 2; //calculate the current index of array 2 after splitting.
        // Calculate the current index of array 2 after splitting it.
        var idx2 = (( + + 1) / 2) - idx1; //when array 2 is split to the left, the current index is calculated.
        //When the maximum value on the left of array 2 is greater than the minimum value on the right of array 1, the left pointer advances to the right.
        if (idx2 ! = 0 && idx1 ! = && nums2[idx2 - 1] > nums1[idx1])
        {
            idxLeft = idx1 + 1;
        }
        // When the maximum value on the left of array1 is greater than the minimum value on the right of array2, the right pointer advances to the left
        else if (idx1 ! = 0 && idx2 ! = && nums1[idx1 - 1] > nums2[idx2])
        {
            idxRight = idx1 - 1;
        }
        else
        {
            // leftMax
            int leftMax.
            //If the split is to the left of array 1, i.e., the current index of array 1 is 0, then the leftMax is taken directly from array 2
            if (idx1 == 0)
            {
                leftMax = nums2[idx2 - 1];
            }
            //If the leftmost of array 2 is separated, i.e., the current index of array 2 is 0, then the leftMax is taken directly from array 1.
            else if (idx2 == 0)
            {
                leftMax = nums1[idx1 - 1]; }
            }
            //otherwise the leftMax is the larger value of the left side of array1 and array2
            else
            {
                leftMax = (nums1[idx1 - 1], nums2[idx2 - 1]); }
            }
            // If the array is computed, the leftMax value is returned directly, ending the computation
            if (( + ) % 2 == 1)
            {
                return leftMax;
            }
            // rightMin
            int rightMin.
            // If the array is separated to the right, i.e., the index of array 1 is its own length, then the right minimum is taken directly from array 2
            if (idx1 == )
            {
                rightMin = nums2[idx2];
            }
            // if separated to the rightmost side of the array, i.e., array2 index is its own length, then the right minimum is taken directly from array1
            else if (idx2 == )
            {
                rightMin = nums1[idx1];
            }
            //otherwise, the right minimum is the smaller of array1 and array2
            else
            {
                rightMin = (nums2[idx2], nums1[idx1]); }
            }
            return (leftMax + rightMin) / 2.0;
        }
    }
    return 0.0; }
}

benchmarking

Finally, we come to a set of benchmark comparison test for six kinds of solutions, each method is divided into three groups of tests, three groups respectively, that the array size of 100, 1000, 10000, and the generation of the two arrays will be randomly controlled as 99 or 100, 999 or 1000, 9999 or 10000, even if it gets the parity of random, and at the same time for each group of randomly generated 10000 groups of test data, the Comparison test. Test results are as follows.

The performance can be found through testing as follows:

Solution 6 Double Pointer + Dichotomous Finding Equalization > Solution 4 Double Pointer + Dichotomous Exclusion > Solution 5 Double Pointer + Dichotomous Finding the Kth Fractional Method > Solution 3 Double Pointer + Direct Fetching > Solution 2 Double Pointer + Merge Arrays > Solution 1 Recreational Method (Built-in Method), it is normal for the Dichotomous Finding of the Kth Fractional Method to be a little bit worse than Dichotomous Exclusion; after all, it calls it twice! algorithm.

classifier for sums of money: The test method code as well as the sample source code have been uploaded to the code repository for those who are interested./hugogoos/Planner