[算法] leetcode golang 4. 寻找两个正序数组的中位数 3种解法 暴力/第k个最小数字/二分

[算法] leetcode golang 4. 寻找两个正序数组的中位数 3种解法 暴力/第k个最小数字/二分

思路1: 暴力(击败55%)

//思路1: 将2个数组合并为一个新的数组然后取中位数//合并 O(n),O(n) 不符合要求//计算 O(1)func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {//合并nums3 := make([]int, len(nums1)+len(nums2))p1, p2, p3 := 0, 0, 0for p3 < len(nums3) {for p1 < len(nums1) && (p2 == len(nums2) || nums1[p1] <= nums2[p2]) {nums3[p3] = nums1[p1]p3++p1++}for p2 < len(nums2) && (p1 == len(nums1) || nums1[p1] > nums2[p2]) {nums3[p3] = nums2[p2]p3++p2++}}//取出中间值mid := len(nums3) / 2left, right := nums3[mid], nums3[mid]//如果是偶数if len(nums3)&1 == 0 {left = nums3[mid-1]}// 最后计算值return (float64(left) + float64(right)) / 2}

思路2: 2个排序数组中寻找第k个元素

时间O(n+m),空间O(1) 不符合要求, 击败 95%

//思路2: 2个排序数组中寻找第k个元素(击败99%)func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {//总长度total := len(nums1) + len(nums2)//总长度的一半mid := total / 2if total & 1 == 1 {//如果是奇数,就是中间那个数字return float64(getKth(nums1,nums2,mid))}else {//如果是偶数,就是中间那2个数的平均数return (float64(getKth(nums1,nums2,mid))+float64(getKth(nums1,nums2,mid-1)))/2.0}}//2个排序数组中寻找第k个元素,k [0,k]func getKth(nums1 []int, nums2 []int, k int)int{//参数处理if len(nums1) == 0{return nums2[k]}if len(nums2) == 0{return nums1[k]}index1,index2 := 0,0kth := 0for ;k != -1;k-- {if index1 == len(nums1){kth = nums2[index2]index2++}else if index2 == len(nums2){kth = nums1[index1]index1++}else if nums1[index1] <= nums2[index2]{kth = nums1[index1]index1++}else {kth = nums2[index2]index2++}}return kth}

思路3: 二分法,复杂度O(log(n+m))

使用二分的方法在2个排序数组中找到K个元素