Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

📢 preface

  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch the card for the fourth day 🎈!
  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻

🌲 Example of original problem

Given two positive-ordered (from small to large) arrays of size m and n, nums1 and nums2. Please find and return the median of the two positive ordinal groups.

Example 1:

Input: nums1 = [1,3], nums2 = [2]

Description: merge array = [1,2,3], median 2

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]

Description: merge array = [1,2,3,4], median (2 + 3) / 2 = 2.5

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]

Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]

Output: 1.00000 Example 5:

Input: nums1 = [2], nums2 = [] Output: 2.00000

Tip:

  • nums1.length == m

  • nums2.length == n

  • 0 <= m <= 1000

  • 0 <= n <= 1000

  • 1 <= m + n <= 2000

  • -106 <= nums1[i], nums2[i] <= 106

🌻C# method 1: merge List to find median by length

Their thinking

New a List, add nums1 and nums2 to the List, and sort. For the sorted list, calculate the median index according to the length, and then calculate the final result.

If the combined list length is 13, then the seventh digit from the smallest to the largest is the median, resultIndex=6.

Assume that the length of the combined list is 14, then the average of the 7th and 8th digits from the smallest to the largest is the median, and the index is 6 and 7 respectively. In this case,resultIndex =7, resultindex-1 =6, the result is (list[resultindex-1] + list[resultIndex]) / 2.0;

public class Solution {
     public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        int m = nums1.Length;
        int n = nums2.Length;
        int len = m + n;
        var resultIndex = len / 2;
        List<int> list = new List<int>(nums1);
        list.AddRange(nums2);
        list.Sort();
        if (len % 2= =0)
        {
            return (list[resultIndex - 1] + list[resultIndex]) / 2.0;
        }
        else
        {
            returnlist[resultIndex]; }}}Copy the code

The execution result

The execution time was 108ms, and the memory consumption was 28 MB.

Time complexity: O((m+n)(1+log(m+n))) add two arrays of length M and n to the list, the complexity is constant level M and n respectively; The complexity of the list. The Sort () according to the official documentation available for (m + n) log (m + n), so the method of time complexity is O (m + n + (m + n) log (m + n)) = O ((m + n) (1 + log (m + n)))

Space complexity: O(m+n) uses a list of m+n lengths.

🌻C# method 1: find the median by length after merge sort

List.sort () is used to Sort the list, but if nums1 and nums2 are unordered, list.sort () is useful. In this case, nums1 and nums2 are ordered arrays, so using list.sort () is a waste of efficiency. We can use the condition that nums1 and nums2 are ordered arrays to simplify our sorting.

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        // nums1 and nums2 are added to the list in order
        List<int> list = new List<int> ();int i = 0, j = 0;
        int m = nums1.Length;
        int n = nums2.Length;
        int len = m + n;
        var resultIndex = len / 2;

        while (i < m && j < n)
        {
            if (nums1[i] < nums2[j])
                list.Add(nums1[i++]);
            else
                list.Add(nums2[j++]);
        }
        while (i < m) list.Add(nums1[i++]);
        while (j < n) list.Add(nums2[j++]);

        if (len % 2= =0)
        {
            return (list[resultIndex - 1] + list[resultIndex]) / 2.0;
        }
        else
        {
            returnlist[resultIndex]; }}}Copy the code

Result the execution result passes. The execution time is 112ms, and the memory consumption is 28.1MB

Time complexity: O(m+n) I and J traverse two arrays of length m and n together, so the time complexity is O(m+n).

Space complexity: O(m+n) uses a list of m+n lengths.

🌻Java method one: binary search (official solution)

Given two ordered arrays, it is required to find the median of two ordered arrays. The most intuitive idea is as follows:

  • Use merge method, merge two ordered array, get a large ordered array. The middle element of a large ordered array is the median.

  • Instead of merging two ordered arrays, just find the location of the median. Since the lengths of the two arrays are known, the sum of the subscripts corresponding to the median is also known. Maintain two Pointers, starting at the subscript 00 of each array, moving the pointer to the smaller value back one bit at a time (if one pointer has reached the end of the array, you only need to move the pointer to the other array) until you reach the median.

Suppose the length of two ordered arrays is mm and NN respectively. What is the complexity of these two ideas?

The time complexity of the first idea is O(m+n)O(m+n), and the space complexity is O(m+n)O(m+n). The second approach can reduce the spatial complexity to O(1)O(1), but the time complexity is still O(m+n)O(m+n).

How to reduce the time complexity to O(\log(m+n))O(log(m+n))? If the time complexity requirements have \loglog, usually need to use binary search, this problem can also be achieved by binary search.

According to the definition of the median, when m+nm+n is odd, the median is the (m+n)/2(m+n)/2 element in two ordered arrays, and when m+nm+n is even, The median is the average of the (m+n)/2(m+n)/2 element and the (m+n)/2+1(m+n)/2+1 element in two ordered arrays. So this problem can be converted to finding the KKTH smallest number in two ordered arrays, where kk is (m+n)/2(m+n)/2 or (m+n)/2+1(m+n)/2+1.

Suppose two ordered arrays are \text{A}A and \text{B}B. To find the KKTH element, we can compare \text{A}[k/2-1]A[k/2−1] with \text{B}[k/2-1]B[k/2−1], where // represents integer division. Because \ text {A}] [k / 2-1 A and \ [k / 2-1] text {B}] [k / 2-1 k / 2-1 B respectively \ in front of the text {A} [0,…, k / 2-2] A [0.. k / 2-2] and \ text {B} [0,…, k / 2-2 B / 2-2] [0.. k, namely k / 2 k / 2-1-1 element, for \ text {A}] [k / 2-1 A and \ [k / 2-1] text {B}] [k / 2-1 k / 2-1 B, the smaller the value There can be at most (k/2-1)+(k/2-1) \leq k-2(K /2−1)+(k/2−1)≤k−2 elements smaller than it, then it cannot be the KKTH smallest number.

Therefore, we can summarize three cases:

  • If \ text {A} < \ [k / 2-1] text {B}] [k / 2-1 A/k / 2-1 < B/k / 2-1, If \text{A}[k/2-1]A[k/2−1] is smaller than \text{A}[k/2-1]A[k/2−1] only \text{A}A and \text{B}B before the k/ 2-1K /2−1 number, \text{A}[k/2-1]A[k/2−1] A[k/2−1] A[k/2−1] [k/2−1] [k/2−1] \text{A}[0]A[0] to \text{A}[k/2-1]A[k/2−1]

  • If \ text {A} > \ [k / 2-1] text {B}] [k / 2-1 A/k / 2-1 > B/k / 2-1, you can eliminate \ text {B} [0] to [0] B \ text {B}] [k / 2-1 k / 2-1 B.

  • If \ text {A} = \ [k / 2-1] text {B}] [k / 2-1 k / 2-1 = B/k / 2-1, can be classified as the first case processing.

\text{A}[k/2-1]A[k/2−1] and \text{B}[k/2-1]B[k/2−1]. At the same time, we will continue the binary search on the new array after exclusion and decrease the value of kk based on the number of excluded numbers, because none of the excluded numbers is larger than the smallest number in kk.

The following three cases need special treatment:

  • If \text{A}[k/2-1]A[k/2−1] or \text{B}[k/2-1]B[k/2−1] is out of bounds, then we can pick the last element in the corresponding array. In this case, we must decrease the value of kk according to the number of excluded numbers, instead of directly subtracting kk from k/2k/2.

  • If an array is empty, all elements in that array are excluded. We can return the KKTH smallest element in the other array.

  • If k is equal to 1 and k is equal to 1, we just return the minimum value of the first element of both arrays.

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

A: 1 3 4 9

B: 1 2 3 4 5 6 7 8 9

The length of the two ordered arrays is 44 and 99 respectively, the sum of the lengths is 1313, and the median is the 77th element in the two ordered arrays, so we need to find the element k=7k=7.

Compare two ordered arrays with subscripts k/2-1=2k/2−1=2, i.e. \text{A}[2]A[2] and \text{B}[2]B[2], as shown below:

A: 1 3 4 9

   ↑
Copy the code

B: 1, 2, 3, 4

Because \ text {A} [2] > \ text {B} [2] A [2] > B [2], and thus eliminate \ text {B} [0] to [0] B \ text {B} [2], [2] B \ text namely array subscript {B} B offset (offset) to 33, Update the value of kk: k= k-K /2= 4K = K − K /2=4.

The next step is to find and compare the numbers with subscripts k/2-1=1k/2−1=1 in two ordered arrays, namely \text{A}[1]A[1] and \text{B}[4]B[4], as shown below, where the square brackets represent the numbers that have been excluded.

A: 1 3 4 9

 ↑
Copy the code

B: [1, 2, 3]

\text{A}[1] < \text{B}[4]A[1]<B[4], exclude \text{A}[0]A[0] to \text{A}[1]A[1], i.e. array \text{A}A subscript offset to 22, and update kk: K = k – k / 2 = 2 k = k – k / 2 = 2.

The next step is to find and compare the numbers in two ordered arrays whose subscripts are K /2-1= 0K /2−1=0, that is, to compare \text{A}[2]A[2] with \text{B}[3]B[3], as shown below, where the square brackets represent the numbers that have been excluded.

A: [1 3] 4 9

     ↑
Copy the code

B: [1, 2, 3]

\text{A}[2]=\text{B}[3]A[2]=B[3]; \text{A}[2]= B[3]; \text{A}[2]= B[3]; K = k – k / 2 = k = k – 1 k / 2 = 1.

\text{A}[3] > \text{B}[3]A[3]>B[3], So the KKTH number is \text{B}[3]=4B[3]=4.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2= =1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            returnmedian; }}public int getKthElement(int[] nums1, int[] nums2, int k) {
        /* To find the element with the KTH (k>1) smallest, Compare pivot1 = NUMs1 [K /2-1] with Pivot2 = nums2[K /2-1] * the "/" here indicates that the elements less than or equal to nums1 are divided by * NUMs1 [0.. k/2-2] K /2-1 * Nums2 elements less than or equal to pivot2 include nums2[0.. k/2-2], a total of K /2-1 * Take pivot = min(pivot1, pivot2), The number of elements less than or equal to Pivot in both arrays will not exceed (k/2-1) + (k/2-1) <= K-2 * so that pivot itself can only be the smallest element in k-1 * If Pivot = Pivot1, Then nums1[0.. k/2-1] cannot be the KTH smallest element. If pivot = Pivot2, nums2[0.. k/2-1] cannot be the KTH smallest element. Since we "deleted" some elements (all of which are smaller than the KTH element), we need to change the value of k minus the number of deleted elements */

        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;
        int kthElement = 0;

        while (true) {
            // The boundary condition
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            
            // Normal condition
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}

链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/

Copy the code

Result the execution result passes. The execution time is 2ms, and the memory consumption is 39.9MB

Complexity analysis

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

🌻Java method two: the KTH decimal

So, neither of these two ideas is going to be in order log of m plus n, order log of m plus n. When we look at the log, it’s obvious that we can only do this by using the binary method. So another way to think about it is, they’re finding the median, which is really just a special case of finding the KTH decimal, and there’s an algorithm for finding the KTH decimal.

In solution two, we’re just going to get rid of the values that can’t be the median, so we’re going to get rid of them one by one. And since the sequence is ordered, we can eliminate it half and half. So let’s say we want to find the KTH decimal, we can eliminate the k over 2 numbers every time we go through the loop. Let’s look at an example.

Let’s say we’re looking for the seventh smallest number.

We compare the k/ 2nd digit in both arrays and round down if k is odd. That is, the 33rd digit, 44 in the top array and 33 in the bottom array, if either of them is small, it means that none of the first K /2 digits in the array is the KTH smallest digit, so it can be excluded. So 11,22,33 can’t be the 77th smallest number, so we can get rid of that. Compare the two arrays 13491349 and 4567891045678910 as new arrays.

More generally A[1], A[2], A[3], A[k/2]… , B[1], B[2], B[3], B[k/2]… , if A[k/2]<B[k/2], then A[1], A[2], A[3], A[k/2] cannot be the KTH smallest number.

In the array A, there are k/2-1 numbers smaller than A[k/2], and in the array B, B[k/2] is smaller than A[k/2], assuming that the numbers before B[k/2] are smaller than A, there are only K /2-1 numbers. So the number less than A[k/2] is at most k/1-1+k/2-1=k-2, so A[k/2] is at most k-1st smallest. And anything less than A[k/2] is unlikely to be the KTH smallest number, so we can rule them out.

The orange part represents the numbers that have been removed.

Since we’ve already excluded three digits, which must be the first digit, in the two new arrays, we just need to look for the smallest number 7 minus 3 = 4, which is k = 4. Now the two arrays compare the second number, 3 is less than 5, so we can get rid of the 1 and 3 in the smaller array.

We’ve eliminated 2 more numbers, so now we’re looking for the number 4 minus 2 is 2. K / 2 = 1; 4 == 4; And since these two numbers are equal, it doesn’t matter which array we get rid of, because if we get rid of one we always get rid of one, so it doesn’t matter. Let’s just assume that 4 is greater than 4 for the sake of consistency, so let’s get rid of this 4 right here.

We’re looking for the smallest number since we’re removing one more number, so we just need to figure out which number is the smallest in both arrays, which is 4.

So the seventh smallest number is 4.

We’re always going to be comparing k over 2, and sometimes we’re going to have arrays that are smaller than k over 2.

So k over 2 is equal to 3, and this array up here has length 2, so we just point at the end of it. In this case, since 2 is less than 3, the above array 1 and 2 will be excluded. Cause the situation down here.

Since two elements are excluded, k is equal to 5, and since the upper array is empty, we only need to return the fifth digit of the lower array.

As can be seen from the above, it does not affect our algorithm whether we find the odd or even number, and during the algorithm, the value of k may change from odd to even, and eventually will change to 1 or return the result directly because an array is empty.

So we use recursive thinking, in order to prevent the array length is less than k/2, so every time we compare the number of min(k/2, len(array) corresponding to the number of the small array excluded, two new arrays into the recursion, and k minus the number of excluded numbers. The recursive exit is when k is equal to 1 or one of the numbers has length 0.

code

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    // Combine even and odd cases. If odd, the same k is evaluated twice.
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 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;
        // Make len1 less than len2, so that if an array is empty, it must be len1
        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)); }} Link: HTTPS://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

Copy the code

Result the execution result passes. The execution time is 2ms, and the memory consumption is 39.8MB

Complexity analysis

Time complexity: O(log(m+n) O(log(m+n) Space complexity: O(1)

💬 summary

  • Today is the fourth day of buckle algorithm clocking! Today’s problem is a little difficult, with the help of force buckle god problem solution looked along while!
  • This paper uses C# and Java programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!