LeetCode - #4 求两个有序数组的中间值

简介: 不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。

前言

我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新了 3 期,我们会保持更新时间和进度(周一、周三、周五早上 9:00 发布),每期的内容不多,我们希望大家可以在上班路上阅读,长久积累会有很大提升。

不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。

难度水平:困难

描述

已知两个有序数组 nums1nums2,他们的数据长度分别是 nm,将两个数组合并成一个新数组,返回新数组的中间值。

整体的运行时间复杂度应该是 O(log (m+n))

示例

示例 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

答案

 class Solution {
   
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
   
        let m = nums1.count
        let n = nums2.count

        if m > n {
   
            return findMedianSortedArrays(nums2, nums1)
        }

        var halfLength: Int = (m + n + 1) >> 1
        var b = 0, e = m
        var maxOfLeft = 0
        var minOfRight = 0

        while b <= e {
   
            let mid1 = (b + e) >> 1
            let mid2 = halfLength - mid1

            if mid1 > 0 && mid2 < n && nums1[mid1 - 1] > nums2[mid2] {
   
                e = mid1 - 1
            } else if mid2 > 0 && mid1 < m && nums1[mid1] < nums2[mid2 - 1] {
   
                b = mid1 + 1
            } else {
   
                if mid1 == 0 {
   
                    maxOfLeft = nums2[mid2 - 1]
                } else if mid2 == 0 {
   
                    maxOfLeft = nums1[mid1 - 1]
                } else {
   
                    maxOfLeft = max(nums1[mid1 - 1], nums2[mid2 - 1])
                }

                if (m + n) % 2 == 1 {
   
                    return Double(maxOfLeft)
                }

                if mid1 == m {
   
                    minOfRight = nums2[mid2]
                } else if mid2 == n {
   
                    minOfRight = nums1[mid1]
                } else {
   
                    minOfRight = min(nums1[mid1], nums2[mid2])
                }

                break
            }
        }
        return Double(maxOfLeft + minOfRight) / 2.0
    }
}
  • 时间复杂度:O(log(n + m))
  • 空间复杂度:O(1)
  • 主要思想:** 对于 m 和 n 数字的数组,nums1nums2,其中 m <= n。要在 nums1 中找到 mid1 的索引,将数组分成左右部分:

nums1[0, 1, ..., mid1 - 1] | nums1[mid1, mid1 + 1, ..., m]

nums2[0, 1, ..., mid2 - 1] | nums2[mid2, mid2 + 1, ..., n]

数组分后的左右部分要确保:

  • 左数 = 右数
  • 左边的最大值 <= 右边的最小值

点击前往 LeetCode 练习

该算法题解的 github 仓库地址是:https://github.com/soapyigu/LeetCode-Swift

相关文章
|
1月前
leetCode(删除有序数组中的重复项)
如何在不使用额外空间的情况下,通过双指针法原地删除有序数组中的重复项。
33 2
|
3月前
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
|
1月前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
40 0
|
3月前
|
算法
LeetCode第26题删除有序数组中的重复项
这篇文章介绍了LeetCode第26题"删除有序数组中的重复项"的解题方法,通过使用双指针技巧,高效地去除数组中的相邻重复元素。
LeetCode第26题删除有序数组中的重复项
|
3月前
|
算法
LeetCode第80题删除有序数组中的重复项 II
文章介绍了LeetCode第80题"删除有序数组中的重复项 II"的解法,利用双指针技术在O(1)空间复杂度内原地删除重复元素,并总结了双指针技术在处理有序数组问题中的应用。
LeetCode第80题删除有序数组中的重复项 II
|
3月前
|
Python
【Leetcode刷题Python】977. 有序数组的平方
解决LeetCode "有序数组的平方" 问题的方法:使用Python内置的快速排序、直接插入排序(但会超时)和双指针技术,并给出了每种方法的Python实现代码。
21 1
【Leetcode刷题Python】977. 有序数组的平方
|
3月前
|
算法
LeetCode第88题合并两个有序数组
文章分享了LeetCode第88题"合并两个有序数组"的解法,通过从后向前的合并策略避免了数组元素的前移,使用三个指针高效地完成了合并过程。
|
3月前
|
Python
【Leetcode刷题Python】108. 将有序数组转换为二叉搜索树
LeetCode上108号问题"将有序数组转换为二叉搜索树"的Python实现,通过递归选取数组中间值作为根节点,构建高度平衡的二叉搜索树。
26 2
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
54 0
|
3月前
|
Python
【Leetcode刷题Python】26. 删除有序数组中的重复项
本文提供了一种使用快慢指针法在原地删除升序数组中重复元素的Python实现,返回删除后数组的新长度,同时保持元素的相对顺序。
44 0