leetcode 4 寻找两个正序数组的中位数

letterbeezps · · 571 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

# leetcode 4 寻找两个正序数组的中位数 ## 分析 这题要求时间复杂log(m+n),所以要想达到这个目标,自然是 二分查找 可以将题目理解为 两个正序数组的第K大数 ```go func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { total := len(nums1) + len(nums2) if total % 2 == 0 { // 偶数长度,取中间两个数 left := findKthNumber(nums1, 0, nums2, 0, total / 2) right := findKthNumber(nums1, 0, nums2, 0, total / 2 + 1) return float64(left + right) / 2 } else { // 奇数长度,取中数 return float64(findKthNumber(nums1, 0, nums2, 0, total / 2 + 1)) } } // 从nums1[i:] 和 nums2[j:]之间找到第k大数 func findKthNumber(nums1 []int, i int, nums2 []int, j int, k int) int { // 提前预处理,默认nums1待处理长度小于nums2 if len(nums1) - i > len(nums2) - j { return findKthNumber(nums2, j, nums1, i, k) } // 边界场景1 if len(nums1) == i { return nums2[j+k-1] } // 边界场景2 if k == 1 { return min(nums1[i], nums2[j]) } si := min(i + k / 2, len(nums1)) sj := j + k / 2 // 二分 if nums1[si-1] > nums2[sj-1] { return findKthNumber(nums1, i, nums2, sj, k - k / 2) } else { return findKthNumber(nums1, si, nums2, j, k - (si - i)) } } func min(a int, b int) int { if a < b { return a } return b } ```

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

571 次点击  
加入收藏 微博
1 回复  |  直到 2022-02-19 16:15:03
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传