LeetCodeTencent--004は2つの正の配列の中位数を探します

タイトル

題番号:4

難易度:困難

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

mとnのサイズの2つの秩序配列nums 1とnums 2が与えられる.
この2つの秩序配列の中位数を見つけ,アルゴリズムの時間的複雑さをO(log(m+n))とすることを要求してください.
nums 1とnums 2が同時に空にならないと仮定できます.
例1:

nums1 = [1, 3]
nums2 = [2]
​
      2.0

例2:

nums1 = [1, 2]
nums2 = [3, 4]
​
      (2 + 3)/2 = 2.5

 
インプリメンテーション
1つ目:二分戦略の利用
中央値:1つのセットを2つの長さの等しいサブセットに分割します.1つのサブセットの要素は常に別のサブセットの要素より大きいです.
問題は時間的複雑度がO(log(m+n))であることが要求されるため,2つの秩序配列の先頭と末尾から中位数(複雑度O(m+n))を1回ずつ見つけることはできない.2点戦略ではなく、比較するたびに比例して数字のセットを直接消すことができ、最後に中位数(複雑度O(log(m+n))を見つけることができます.

nums1: [a1,a2,a3,...am]
nums2: [b1,b2,b3,...bn]
​
[nums1[:i],nums2[:j] | nums1[i:], nums2[j:]]
​
nums1   i       
nums2   j = (m+n+1)/2 - i     

左右の個数が同じであることを保証すれば、中位数は|という境界のそばで発生し、二分法を利用して適切なiを見つけることができる.

状態:

経由

2085/2085試験例

実行時間:160 ms、すべてのC#コミットで99.18%のユーザー

を破った.

メモリ消費量:26.8 MB、すべてのC#コミットで5.05%のユーザー

を破った

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.Length;
        int n = nums2.Length;
        if (m > n)
            return FindMedianSortedArrays(nums2, nums1);
​
        int k = (m + n + 1)/2;
        int left = 0;
        int right = m;
        while (left < right)
        {
            int i = (left + right)/2;
            int j = k - i;
            if (nums1[i] < nums2[j - 1])
                left = i + 1;
            else
                right = i;
        }
        int m1 = left;
        int m2 = k - left;
        int c1 = Math.Max(m1 == 0 ? int.MinValue : nums1[m1 - 1],
            m2 == 0 ? int.MinValue : nums2[m2 - 1]);
​
        if ((m + n)%2 == 1)
            return c1;
​
        int c2 = Math.Min(m1 == m ? int.MaxValue : nums1[m1],
            m2 == n ? int.MaxValue : nums2[m2]);
        return (c1 + c2)*0.5;        
    }
}

 
 
2つ目は、整列配列にマージする方法です.
構想:まず2つの秩序配列を1つの秩序配列に結合し、配列長に基づいて中位数を決定し、配列長が偶数の場合、2つの中位数の平均値を返し、配列長が奇数の場合、中位数を返します.
python実装

実行結果:

経由

実行時間:128 ms、すべてのPython 3コミットで34.35%のユーザー

を破った.

メモリ消費量:12.8 MB、すべてのPython 3コミットで99.43%のユーザー

を破った.

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        m = len(nums1)
        n = len(nums2)
        nums1.extend(nums2)#   
        nums1.sort()#           
        if (m + n) & 1:#            
            return nums1[(m + n - 1) >> 1]
        else:#            
            return (nums1[(m + n - 1) >> 1] + nums1[(m + n) >> 1]) / 2
​

C#実装

状態:

経由

2085/2085試験例

実行時間:188 ms、すべてのC#コミットで72.14%のユーザー

を破った.

メモリ消費量:26.9 MB、すべてのC#コミットで5.05%のユーザー

を破った

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.Length;
        int len2 = nums2.Length;
        int len = len1 + len2;
        int[] nums = new int[len];
        Array.Copy(nums1, nums, len1);
        Array.Copy(nums2, 0, nums, len1, len2);
        Array.Sort(nums);
        if (len%2 == 0)
        {
            return (nums[len/2] + nums[len/2 - 1])*0.5;
        }
        return nums[len/2];        
    }
}