Median of Two Sorted Arrays

質問リンク:https://leetcode.com/problems/median-of-two-sorted-arrays/

1.問題の特定

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
すなわち,配列の長さがそれぞれmとnの場合,2つの配列を結合し,並べ替えて中心値を返す.

1-1. 条件

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

1番目の配列の長さはm,2番目の配列の長さはnである.mとnは0以上1000以下である.mとnの和は1以上2000以下である.各配列のインデックス値は−106以上106以下である.

1-2. 例

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (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

2.解答

まず、私の答えを見てみましょう.

2-1. 私の答え

まず私の最初の解決方法です.

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums = nums1 + nums2
        nums.sort()
        i, j = divmod(len(nums), 2)
        
        if j == 0:
            return (float(nums[i-1]) + float(nums[i])) / 2
        else:
            return nums[i]

1つ目は,受け取った関数パラメータとしての配列nums 1とnums 2を結合して並べ替え,divmodを用いてiとjにそれぞれ2に分かれたシェアと残数を入れる.
残りの値が0の場合、Example 2と同じ中間値を指定する必要があります.したがって、i-1とiの2番目のインデックス値を加算し、2で割った値を返します.逆に、残りが1の場合、iインデックスが返されます.

次は私の2番目の解決方法です.

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums = nums1 + nums2
        nums.sort()
        i = len(nums) / 2
        
        if len(nums) % 2 == 0:
            return (float(nums[i-1]) + float(nums[i])) / 2
        else:
            return nums[i]

第1の解との違いは,divmodを用いず,iにnums配列の長さを2で割ったシェアのみを加え,nums配列の長さを2の倍数と非倍数で割って計算することである.

1つ目に比べて、メモリと速度の面でいくつかの進歩があります.