LeetCode 4. Find the median of two positive ordinal groups

Table of contents: Algorithm Diary

4. Find the median of two positive Ordinal Numbers (LeetCode) (leetcode-cn.com)

Topic describes

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.

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

Data range

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

The subject sample

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

Algorithm ideas

Given two positive ordinal nums1nums1nums1 and nums2nums2nums2, let the corresponding array lengths be len1Len1Len1 and len2Len2Len2. Let’s say len is equal to len1 plus len2len is equal to len1 plus len2len is equal to len1 plus len2. Finding the median of two positive ordinal groups is equivalent to finding the number KKK (k starts from 1) small in two positive ordinal groups. Let f(k) F (k)f(k) represent the number KKK small in two positive ordinal groups:

• When lenlenlen is odd, k=⌊len/2⌋+ 1K = \lfloor len/2 \rfloor + 1K =⌊len/2⌋+1, the median is f(k)f(k)f(k);
• If lenlenlen is even, k1=len/2,k2=len/2+1k_1 =len/2, K_2 =len/2+ 1k1=len/2 +1,k2=len/2+1, Median (f (k1) + f (k2)) / 2 (f (k_1) + f (k_2)) / 2 (f (k1) + f (k2)) / 2;

Len1

In general, there are three conditions when Len1 >⌊k/2⌋len1 > \ LFloor K /2 \rfloorlen1>⌊k/2⌋ and Len2 > \ lFloor K /2 \rfloorlen2> \ LFloor K /2 \rfloorlen2> \ lFloor K /2 \

1. Nums1 [L1 +⌊k/2⌋]
2. Nums1 [L1 +⌊k/2⌋]> NUMs2 [L2 +⌊k/2⌋]nums1[L1 + \ lFloor K /2 \rfloor] >nums2[l2+ \lfloor K /2 Nums1 \ rfloor] [l1 + / 2 ⌋ ⌊ k] > nums2 l2 + ⌊ k / 2 ⌋, In this case, the median must not be in the range nums2[l2, L2 +⌊k/2⌋] NUMs2 [L2, L2 + \lfloor K /2 \rfloor]nums2[L2, L2 +⌊k/2⌋], so the range can be left out.
3. Nums1 [L1 +⌊k/2⌋]= NUMs2 [l2+⌊k/2⌋] Nums1 [L1 + \lfloor K /2 \rfloor] =nums2[l2+ \lfloor K /2 \rfloor]nums1[L1 +⌊k/2⌋]=nums2[l2+⌊k/2⌋].

After each deletion, the value of KKK decreases the length of deletion, which turns into a recursive subproblem. It is equivalent to cutting either NUMs1NUMs1NUMs1 or NUMs2NUMs2NUMs2 in half each time. The time complexity meets the requirements of log(n)log(n)log(n).

Consider special cases:

• Due to the
  $len = len1 + len2, len1 < len2$and
  $K ≤ lfloor len / 2 \rfloor + 1$, so:
  • Len2 >⌊k/2⌋len2 > \lfloor k/2 \rfloorlen2>⌊k/2⌋;
  • When len1<⌊k/2⌋len1 < \lfloor K /2 \rfloorlen1<⌊k/2⌋, all elements in nums1Nums1nums1 are taken out for unified operation;
  • Since len1Len1Len1 is short, combine 1 and 3 in the general case;
• When k=1k =1k =1, according to the KKK decimal definition, nums1NUMs1NUMs1 and nums2NUMs2NUMs2 minimum;
• When nums1NUMs1NUMs1 is divided first, directly return nums2NUMs2nums2 KKK element;

AC code

/ * * *@param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}* /
var findMedianSortedArrays = function(nums1, nums2) {
    let len = nums1.length + nums2.length;
    if(len % 2= =1) { 
        return find(nums1, 0, nums2, 0, (len >> 1) + 1);
    } else {
        // f(k1)
        let left = find(nums1, 0, nums2, 0, (len >> 1)); 
        // f(k2)
        let right = find(nums1, 0, nums2, 0, (len >> 1) + 1); 
        return (left + right) / 2; }};var find = function(nums1, l1, nums2, l2, k) {
    Nums2 is longer than nums1
    if(nums1.length - l1 > nums2.length - l2) return find(nums2, l2, nums1, l1, k);
    // if nums1 has been dropped completely
    if(nums1.length === l1) return nums2[l2 + k - 1]; 
    if(k === 1) return Math.min(nums1[l1], nums2[l2]);
    // Len1 may be less than k
    let tl1 = Math.min(l1 + (k >> 1), nums1.length);
    let tl2 = l2 + (k >> 1);
    // General
    if(nums1[tl1 - 1] > nums2[tl2 - 1]) {
        return find(nums1, l1, nums2, l2 + (k >> 1), k - (k >> 1));
    } else {
        returnfind(nums1, tl1, nums2, l2, k - (tl1 - l1)); }}Copy the code