Junedayday Blog

六月天天的个人博客

0%

Go算法实战 - 4.【寻找两个正序数组的中位数LeetCode-4】

发表于 分类于

Go-Leetcode

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

原题链接 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

1
2
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
}

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	l1, l2 := len(nums1), len(nums2)
	if (l1+l2)%2 == 1 {
		return float64(findKthInSortedArrays(nums1, nums2, (l1+l2)/2+1))
	}
	return float64(findKthInSortedArrays(nums1, nums2, (l1+l2)/2)+findKthInSortedArrays(nums1, nums2, (l1+l2)/2+1)) / 2
}

func findKthInSortedArrays(nums1 []int, nums2 []int, k int) int {
	fmt.Println(nums1, nums2, k)
	length1, length2 := len(nums1), len(nums2)
	if length1 < length2 {
		return findKthInSortedArrays(nums2, nums1, k)
	} else if length2 == 0 {
		return nums1[k-1]
	} else if k == 1 {
		if nums1[0] > nums2[0] {
			return nums2[0]
		}
		return nums1[0]
	}

	// 取i1/i2为k/2，并处理越界
	i1, i2 := k/2, k-k/2
	if i2 > length2 {
		i2 = length2
		i1 = k - length2
	}

	// 截断小的数组后，继续递归查找
	if nums1[i1-1] < nums2[i2-1] {
		return findKthInSortedArrays(nums1[i1:], nums2, k-i1)
	} else if nums1[i1-1] > nums2[i2-1] {
		return findKthInSortedArrays(nums1, nums2[i2:], k-i2)
	}
	return nums1[i1-1]
}

Github: https://github.com/Junedayday/code_reading

Blog: http://junes.tech/

Bilibili: https://space.bilibili.com/293775192

公众号: golangcoding

二维码