题目
文章图片
合并有序数组直接返回中位数
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
var nums3 []int
var a,b int
//合并数组
for a复杂度
时间O（m+n）
空间O（1）
文章图片
【学习二分法的完美例题 leetcode 4 寻找两个正序数组的中位数】合并数组使用了太多时间，将其优化为log
文章图片
文章图片
由于两个数组都为有序数组，在目标数字之前的数都必然小于它，这就允许我们进行快速的排除
定义i，j两个指针，每次排除k/2个必然不是中位数的数，并将指针前移
直到特殊情况找到第k个数
文章图片
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
//find (m+n+1)/2 and (m+n+2)/2
m:=len(nums1)
n:=len(nums2)
res1:=getKthElement(nums1,nums2,(m+n+2)/2)
res2:=getKthElement(nums1,nums2,(m+n+1)/2)
return (float64(res1)+float64(res2))/2
}
func getKthElement(nums1 []int, nums2 []int, k int)int{
var index1,index2 int
for {
//如果一个数组已被排查完，直接返回另一个数组的第k个元素
if index1 == len(nums1) {
return nums2[index2 + k - 1]
}
if index2 == len(nums2) {
return nums1[index1 + k - 1]
}
//如果要找最小的元素，则只有两种可能性，直接比较找到结果
if k == 1 {
return min(nums1[index1], nums2[index2])
}
//更新排除的数k/2，完成比较，排除小于k的数，k值减小
half := k/2
newIndex1 := min(index1 + half, len(nums1)) - 1
newIndex2 := min(index2 + half, len(nums2)) - 1
pivot1, pivot2 := nums1[newIndex1], nums2[newIndex2]
if pivot1 <= pivot2 {
k -= (newIndex1 - index1 + 1)
index1 = newIndex1 + 1
} else {
k -= (newIndex2 - index2 + 1)
index2 = newIndex2 + 1
}
}}
func min(x, y int) int {
if x < y {
return x
}
return y
}
文章图片
推荐阅读
- LeetCode|【刷题1】LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 java题解
- 高级数据结构|浙江省赛 —— E. Easy DP Problem（主席树、维护区间前K大值总和）
- LeetCode刷题笔记|LeetCode刷题笔记（二分查找简单进阶）
- LeetCode刷题笔记|Leetcode刷题笔记（二分查找算法）