IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> LeetCode 寻找两个正序数组的中位数 -> 正文阅读

[数据结构与算法]LeetCode 寻找两个正序数组的中位数

题目
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

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

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

解法:
这题麻烦在想清楚自己切分的中位数是在切分线的左侧还是右侧。
另外就是有些边界条件比较麻烦,我是调试出来的。
核心思想是二分查找法+切分数组:

func Min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}
func Max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    if len(nums1) > len(nums2) {
        return findMedianSortedArrays(nums2, nums1)
    }
    // 二分搜索合适的分割线
    leftA := 0
    rightA := len(nums1) - 1
    midA, midB, k := 0, 0, (len(nums1) + len(nums2)) >> 1

    for {
        midA = (leftA + rightA + 1) >> 1     //中位数索引,偶数时选择右侧的索引
        midB = k - midA

        
        if midA > 0 && nums1[midA-1] > nums2[midB] {
            //分割线需要左移
            rightA = midA-1
        } else if midA != len(nums1) && nums1[midA] < nums2[midB-1] {
            //分割线需要右移
            leftA = midA+1
        } else {
            // 分界线合适
            break
        }
    }
    left, right := 0, 0
    if midA < 0 || midA >= len(nums1) {
        right = nums2[midB]
    } else if midB < 0 || midB >= len(nums2) {
        right = nums1[midA]
    } else {
        right = Min(nums1[midA], nums2[midB])
    }

    if (len(nums1) + len(nums2)) % 2 != 0 {
        return float64(right)
    }

    if midA == 0 {
        left = nums2[midB-1]
    } else if midB == 0 {
        left = nums1[midA-1]
    } else {
        left = Max(nums1[midA-1], nums2[midB-1])
    }
    
    return float64(left + right) / 2
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-11-19 17:52:03  更:2021-11-19 17:54:27 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 12:27:18-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码