“This is the 15th day of my participation in the First Gwen Challenge 2022.First challenge in 2022”

1, the title

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] output: 2.00000 explanation: merge array = [1,2,3], median 2Copy the code

Example 2:

Input: nums1 = [1,2], nums2 = [3,4] output: 2.50000 description: merge array = [1,2,3,4], median (2 + 3) / 2 = 2.5Copy the code

Example 3:

Input: nums1 = [0,0], nums2 = [0,0] output: 0.00000Copy the code

Example 4:

Input: nums1 = [], nums2 = [1] Output: 1.00000Copy the code

Example 5:

Input: nums1 = [2], nums2 = [] Output: 2.00000Copy the code

Tip:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

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

2, train of thought

O(log(n+m))O(log(n+m))O(log(n+m))

Finding the median of two positive Ordinal Numbers is equivalent to finding the KTH decimal in two positive Ordinal Numbers. If the two arrays are of size n and m, then the k = (n + m)/2 decimal is the median.

How do I find the KTH smallest element?

The process is as follows:

1. In the general case, we take the first k/2 elements of nums1 and numS2

By default, nums1 has a smaller effective length than nums2. The effective length of nums1 starts with I and nums2 starts with j, where [I, si-1] is the first K / 2 elements of nums1 and [j, sj-1] is the first K / 2 elements of nums2.

Nums1 [si-1] = nums2[sj-1] = nums1[si-1] = nums2[sj-1]

  • ifnums1[si - 1] > nums2[sj - 1]On the other hand, indicatenums1Too many elements are taken from,nums2Too few elements are taken from. sonums2In the firstk/2All of these elements must be less than or equal to number onekThe decimal, i.e.,nums2[j,sj-1]In the element. So we can get rid of this guy and go to number one in the rest of the intervalk - k / 2The small element, that is, thekSmall must be[i,n]with[sj,m]In the.
  • ifnums1[si - 1] <= nums2[sj - 1], can be explained in the same waynums2In the firstk/2All of these elements must be less than or equal to number onekThe decimal, i.e.,nums1[i,si-1]In the element. So we can get rid of this guy and go to number one in the rest of the intervalk - k / 2The small element, that is, thekSmall must be[si,n]with[j,m]In the.

3. Recursion 2 reduces the size of the problem by half each time, and the last number left is the KTH decimal we are looking for.

Recursive boundary:

  • whennums1When the array is empty, we return it directlynums2The first of an array ofkDecimal.
  • whenk == 1, and neither array is empty, we return the minimum value of the first element of the two arrays, i.emin(nums1[i], nums2[j]).

Parity analysis:

  • When the sum of the two array elements total is even, find the total / 2 small left and total / 2 + 1 small right, the result is (left + right / 2.0).

  • When total is odd, find the smallest total / 2 + 1, which is the result.

Time complexity analysis: k = (m + n) / 2 k = 2 k = (m + n)/(m + n) / 2, and the scale of the recursive KKK every time cut in half, so the time complexity is O (log (m + n) O (log (m + n) O (log (m + n)).

C++ code

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size() + nums2.size(a);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(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
        if (nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);
        if (k == 1) {
            if (nums1.size() == i) return nums2[j];
            else return min(nums1[i], nums2[j]);
        }
        if (nums1.size() == i) return nums2[j + k - 1];
        int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
        if (nums1[si - 1] > nums2[sj - 1])
            return find(nums1, i, nums2, sj, k - (sj - j));
        else
            return find(nums1, si, nums2, j, k - (si - i)); }};Copy the code

4. Java code

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        if(total % 2= =0)
        {
            int left = f(nums1,0,nums2,0,total / 2);
            int right = f(nums1,0,nums2,0,total / 2 + 1);
            return (left + right) / 2.0;
        }
        else return f(nums1,0,nums2,0,total / 2 + 1);
    }
    static int f(int[] nums1,int i,int[] nums2,int j,int k)
    {
        // The first one is small by default
        if(nums1.length - i > nums2.length - j) return f(nums2,j,nums1,i,k);
        // When the first array is used up
        if(nums1.length == i) return nums2[j + k - 1];
        // take the first element
        if(k == 1) return Math.min(nums1[i],nums2[j]);

        int si = Math.min(nums1.length,i + k / 2),sj = j + k - k / 2;
        if(nums1[si - 1] > nums2[sj - 1])
        {
            return f(nums1,i,nums2,sj,k - (sj - j));
        }
        else
        {
            returnf(nums1,si,nums2,j,k - (si - i)); }}}Copy the code

Original link: 4. Find the median of two positive ordinal groups