LeetCode Go — 4. Найдите медиану двух массивов положительного порядка

задняя часть алгоритм
LeetCode Go — 4. Найдите медиану двух массивов положительного порядка

Это 19-й день моего участия в Gengwen Challenge, Подробности о мероприятии см.:Обновить вызов

Для лучшего будущего придерживайтесь чистки зубовLeetCode!

тема

Учитывая два размераmиnмассив положительного порядка (от меньшего к большему)nums1и nums2. Пожалуйста, найдите и верните два массива положительного порядкамедиана.

Пример 1:

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

Пример 2:

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

Пример 3:

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

Пример 4:

输入：nums1 = [], nums2 = [1]
输出：1.00000

Пример 5:

输入：nums1 = [2], nums2 = []
输出：2.00000

намекать:

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

Решение 1 — объединить массивы

Идеи решения проблем

Насильственное решение состоит в том, чтобы объединить два массива, а затем найти медиану.

код

func findMedianSortedArrays(nums1, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    nums := make([]int, m + n)
    var i, j int
    for k := 0; k < len(nums); k++ {
        if i < m && j < n {
            if nums1[i] < nums2[j] {
                nums[k] = nums1[i]
                i++ 
            }else {
                nums[k] = nums2[j]
                j++
            }
        }else if i < m {
            nums[k] = nums1[i]
            i++
        }else if j < n {
            nums[k] = nums2[j]
            j++
        }
    }

    if len(nums) % 2 == 0 {
        return float64(nums[len(nums)/2] + nums[len(nums)/2-1])/2
    }
    return float64(nums[len(nums)/2])
}

Результаты

执行用时：16 ms，在所有 Go 提交中击败了 76.44% 的用户
内存消耗：5.7 MB，在所有 Go 提交中击败了 33.51% 的用户

Анализ сложности

  • временная сложность:O(m+n)O(m+n)
  • Сложность пространства:O(m+n)O(m+n)

ссылка на тему

4. Найдите медиану двух массивов положительного порядка.

Категории