Click here to read more about algorithmic interviewing

Topic describes

Given two positively 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.

Advanced: Can you design a time complexity of O(log(m+n))O(log (m+n))O(log(m+n)) to solve this problem?

Example 1:

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

Merge array = [1,2,3], median 2

Example 2:

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

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

Simple solution

If you ignore the order log(m+n))O(log(m +n))O(log(m +n)), this is pretty easy.

An intuitive way to do this is to merge the two arrays, sort them, and average the values of total / 2 and (total-1) / 2.

The purpose of this is to avoid a case-by-case discussion of whether the combined array length is odd or even.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int[] arr = new int[n + m];
        int idx = 0;
        for (int i : nums1) arr[idx++] = i;
        for (int i : nums2) arr[idx++] = i;
        Arrays.sort(arr);
        int l = arr[(n + m) / 2], r = arr[(n + m - 1) / 2];
        return (l + r) / 2.0; }}Copy the code

Time complexity: the complexity of the merger of two arrays is O (m + n) O (m + n) O (m + n), for the complexity of the merger to sort an array is O (log (m + n) (m + n) O ((m + n) log (m + n) O ((m + n) log (m + n)). Overall complexity is O (log (m + n) (m + n) O ((m + n) log (m + n) O ((m + n) log (m + n))

Space complexity: O(1)O(1)O(1)

Note:Arrays.sort()There are not only biaxial quicksort implementations, the complexity analysis here assumes that they use biaxial quicksort.

Divide and conquer method

First, the original problem can be equivalent to: find the KTH smallest number from two ordered arrays.

There are two cases to discuss:

  1. An even total number: Find the (total / 2) smallest and (total / 2 + 1) smallest number, and the result is the average of the two.

  2. An odd total number: the result is the (total / 2 + 1) smallest number.

Specific ideas are as follows:

  • By default, the first array has a shorter effective length than the second, and if not, the two arrays are swapped. (This is also a common trick to reduce boundary-handling: instead of checking for two arrays, you only need to check for the short array.)

  • The effective length of the first array starts with I, and the effective length of the second array starts with j, where [I, si-1] is the first K / 2 elements of the first array, and [j, sj-1] is the first k-k / 2 elements of the second array (to make sure k is odd).

  • Nums1 [si-1] > nums2[sj-1] : indicates that the k-th must not be in [j, sj-1], that is, in [I,n] or [sj,m]

  • Nums1 [si-1] <= nums2[sj-1] : indicates that the KTH is definitely not in [I, si-1], that is, in [si,n] or [j,m]

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int tot = nums1.length + nums2.length;
        if (tot % 2= =0) {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        } else {
            return find(nums1, 0, nums2, 0, tot / 2 + 1); }}int find(int[] n1, int i, int[] n2, int j, int k) {
        if (n1.length - i > n2.length - j) return find(n2, j, n1, i, k);
        if (i >= n1.length) return n2[j + k - 1];
        if (k == 1) {
            return Math.min(n1[i], n2[j]);
        } else {
            int si = Math.min(i + (k / 2), n1.length), sj = j + k - (k / 2);
            if (n1[si - 1] > n2[sj - 1]) {
                return find(n1, i, n2, sj, k - (sj - j));
            } else {
                returnfind(n1, si, n2, j, k - (si - i)); }}}}Copy the code

Time complexity: The size of the recursion K is reduced by half each time to O(log(m+n))O(log(m +n))O(log(m +n))

Space complexity: O(1)O(1)O(1)

conclusion

For today’s problem, I’ve introduced you to two techniques:

  1. In machine trials or weekly tournaments, the goal is to get the AC as fast as possible, so Java can simply not write the private modifier (not writing means using the default package permissions), and this is no problem, no hassle

  2. In the computer test or weekly contest, we encountered some problems that constrained us verbally. For example, this problem restricted us to use the O(log (m+n)) algorithm. It can analyze whether it can be done without the restriction requirements. The specific analysis ideas are as follows:

    2.1 First, there is an algorithm idea that is easy to implement. For example, it is easy to use a double pointer to find the KTH smallest number, which is O(n).

    2.2 Whether the data size of the topic (①) supports us to use an algorithm beyond the limit. For example, the data size is 1000 + 1000 = 2000.

    2.3 According to the data size, judge whether our naive algorithm computer can finish processing ② within 1s, that is, judge whether the number of operations is less than 10^7 ③. For example, in this case, the double-pointer algorithm is used, and the pointer movement and size are calculated in one run. Since the data is only 2000, it is far from 10^7, so it is completely sufficient

Note ① : regular algorithm topics will provide data scale, LeetCode on some old topics did not provide, because the time out is not too standard, LeetCode new topics, other OJ platform topics, algorithm competition topics will have.

Note 2: Even the simplest problems in the strictest OJ will provide 1s of running time, beyond which the timeout is counted.

Note 3: The processing speed within the 1s limit of the calculator is 10^8, but in order to minimize error submissions, try to use the technique compared to 10^7.

Note: I only recommend using these two techniques in computer trials or weekly tournaments (as fast as possible AC scenarios). Practice or interview time must be honest in accordance with the requirements of the topic.

The last

This is the fourth article in our series of “Brush through LeetCode”. The series started on 2021/01/01, and there are 1916 questions in LeetCode by the start date, some of which have locks. We will finish all the questions without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

As the number of LeetCode questions keeps increasing with weekly and biweekly competitions, in order to facilitate our progress statistics, we will calculate the progress according to the total number of questions at the beginning of the series as the denominator and the completed questions as the numerator. Current progress is 4/1916.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: Github address & Gitee address.

In the repository, you’ll see links to the series, the corresponding code for the series, the LeetCode source links, and some other preferred solutions.


# Algorithms and data structures

# LeetCode antithesis

# Algorithmic interview