S2
S2 copied to clipboard
halfrost
0004. Median of Two Sorted Arrays | LeetCode Cookbook
https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0004.Median-of-Two-Sorted-Arrays/
py checkin
if not len(nums1):
return nums2[len(nums2) // 2] if len(nums2) % 2 else (nums2[len(nums2) // 2 - 1] + nums2[len(nums2) // 2]) / 2
if not len(nums2):
return nums1[len(nums1) // 2] if len(nums1) % 2 else (nums1[len(nums1) // 2 - 1] + nums1[len(nums1) // 2]) / 2
if len(nums1) > len(nums2):
t = nums2
nums2 = nums1
nums1 = t
del t
######################################################
left = (len(nums1) + len(nums2)) // 2
leftIn1 = 0 #以中位数左侧的元素个数作标记，leftIn1表示有这么多在nums1列表
#left表示总共有这么多在中位数左边，left - leftIn1就是nums2中的个数
cutPoint1 = 0
cutPoint2 = len(nums1)
while True:
if not leftIn1:
if nums1[leftIn1] < nums2[left - leftIn1 - 1]:
if cutPoint2 < cutPoint1:
cutPoint2 = cutPoint1
#move right
else:
break
elif not left - leftIn1:
if nums1[leftIn1 - 1] > nums2[left - leftIn1]:
if cutPoint2 > cutPoint1:
cutPoint2 = cutPoint1
#move left
else:
break
else:
if nums1[leftIn1] < nums2[left - leftIn1 - 1]:
if cutPoint2 < cutPoint1:
cutPoint2 = cutPoint1
#move right
elif nums1[leftIn1 - 1] > nums2[left - leftIn1]:
if cutPoint2 > cutPoint1:
cutPoint2 = cutPoint1
#move left
else:
break
cutPoint1 = leftIn1
leftIn1 = (cutPoint1 + cutPoint2) // 2
if leftIn1 == cutPoint1:
if cutPoint2 < cutPoint1 and leftIn1:
leftIn1 -= 1
elif cutPoint2 > cutPoint1 and leftIn1 < len(nums1):
leftIn1 += 1
if not leftIn1 or leftIn1 == len(nums1):
break
####################################################
if (len(nums1) + len(nums2)) % 2:
if leftIn1 == len(nums1):
return nums2[left - leftIn1]
if left - leftIn1 == len(nums2):
return nums1[leftIn1]
return min(nums1[leftIn1], nums2[left - leftIn1])
return (max(nums1[leftIn1 - 1] if leftIn1 else nums2[left - leftIn1 - 1], nums2[left - leftIn1 - 1] if left - leftIn1 else nums1[leftIn1 - 1]) + min(nums1[leftIn1] if leftIn1 < len(nums1) else nums2[left - leftIn1], nums2[left - leftIn1] if left - leftIn1 < len(nums2) else nums1[leftIn1])) / 2
为什么我的二分搜索这么长……
按s自动跳转搜索框这是什么神秘设定，都打不了单词了
@CHIYOI 我刚刚试了一下，不会自动跳转搜索框呀。你是怎么操作的呢？就只按键盘上的字母键 s ？
按s自动跳转搜索框这是什么神秘设定，都打不了单词了
@CHIYOI 我刚刚试了一下，不会自动跳转搜索框呀。你是怎么操作的呢？就只按键盘上的字母键 s ？
英文输入，就只按s，我是macOS11.5，safari
按s自动跳转搜索框这是什么神秘设定，都打不了单词了
@CHIYOI 我刚刚试了一下，不会自动跳转搜索框呀。你是怎么操作的呢？就只按键盘上的字母键 s ？
英文输入，就只按s，我是macOS11.5，safari
@CHIYOI 我复现了。确实有问题。按 s 和 ？都会有这个问题。（别问我是怎么发现 ？ 也会触发，因为我把键盘上所有的键都按了一遍。😄）我周末查查是什么问题哈~ 感觉是 hugo 框架的问题。
Runtime: 8 ms, faster than 97.53% of Go online submissions for Median of Two Sorted Arrays. Memory Usage: 5.3 MB, less than 82.73% of Go online submissions for Median of Two Sorted Arrays.
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
var (
len1 int = len(nums1)
len2 int = len(nums2)
)
if len1 == 0 && len2 == 0 {
return 0
}
numsT := nums1
if len1 == 0 {
numsT = nums2
}
if len1 == 0 || len2 == 0 {
len3 := len(numsT)
div, mod := len3/2, len3%2
if mod == 0 {
return float64((numsT[div-1] + numsT[div])) / 2
} else {
return float64(numsT[div])
}
} else {
// 思路：
// 已知nums1和nums2均是有序的，可设计一种切换遍历的机制。
// 通过div和mod来判断切换遍历提前结束，并计算中位数。
//
// 结束遍历的判断条件：
// 遍历次数count 等于 div
// 计算中位数：
// 1、mod等于0时，中位数等于当前遍历的数；
// 2、mod等于1时，中位数等于(前一个遍历的数+当期遍历的数)/2；
//
var (
div int = (len1 + len2) / 2
mod int = (len1 + len2) % 2
n int = 0 // nums1_index
m int = 0 // nums2_index
count int = 0
pre = 0
curr = 0
)
for {
// 条件1：nums1已经遍历完，但nums2还没有遍历完，numsT切片切换到nums2。
// 条件2：nums2已经遍历完，但nums1还没有遍历完，numsT切片切换到nums1。
// 条件3：nums1[n]大于等于nums2[n], numsT切片切换到nums2。
// 条件4：nums1[n]小于nums2[n], numsT切片切换到nums1。
if n >= len1 && m < len2 {
numsT = nums2[m:]
m++
} else if m >= len2 && n < len1 {
numsT = nums1[n:]
n++
} else if nums1[n] >= nums2[m] {
numsT = nums2[m:]
m++
} else if nums1[n] < nums2[m] {
numsT = nums1[n:]
n++
}
curr = numsT[0] // 取出0号值
count++ // 遍历了一次
if (count - 1) == div {
break
}
pre = curr
}
// 计算中位数
if mod == 0 {
return float64(pre+curr) / 2
} else {
return float64(curr)
}
}
}
@yshdzw Runtime: 8 ms, faster than 97.53% of Go online submissions for Median of Two Sorted Arrays. Memory Usage: 5.3 MB, less than 82.73% of Go online submissions for Median of Two Sorted Arrays.
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { var ( len1 int = len(nums1) len2 int = len(nums2) ) if len1 == 0 && len2 == 0 { return 0 } numsT := nums1 if len1 == 0 { numsT = nums2 } if len1 == 0 || len2 == 0 { len3 := len(numsT) div, mod := len3/2, len3%2 if mod == 0 { return float64((numsT[div-1] + numsT[div])) / 2 } else { return float64(numsT[div]) } } else { // 思路： // 已知nums1和nums2均是有序的，可设计一种切换遍历的机制。 // 通过div和mod来判断切换遍历提前结束，并计算中位数。 // // 结束遍历的判断条件： // 遍历次数count 等于 div // 计算中位数： // 1、mod等于0时，中位数等于当前遍历的数； // 2、mod等于1时，中位数等于(前一个遍历的数+当期遍历的数)/2； // var ( div int = (len1 + len2) / 2 mod int = (len1 + len2) % 2 n int = 0 // nums1_index m int = 0 // nums2_index count int = 0 pre = 0 curr = 0 ) for { // 条件1：nums1已经遍历完，但nums2还没有遍历完，numsT切片切换到nums2。 // 条件2：nums2已经遍历完，但nums1还没有遍历完，numsT切片切换到nums1。 // 条件3：nums1[n]大于等于nums2[n], numsT切片切换到nums2。 // 条件4：nums1[n]小于nums2[n], numsT切片切换到nums1。 if n >= len1 && m < len2 { numsT = nums2[m:] m++ } else if m >= len2 && n < len1 { numsT = nums1[n:] n++ } else if nums1[n] >= nums2[m] { numsT = nums2[m:] m++ } else if nums1[n] < nums2[m] { numsT = nums1[n:] n++ } curr = numsT[0] // 取出0号值 count++ // 遍历了一次 if (count - 1) == div { break } pre = curr } // 计算中位数 if mod == 0 { return float64(pre+curr) / 2 } else { return float64(curr) } } }
你这时间复杂度是O(n)吧
@CHIYOI 按s自动跳转搜索框这是什么神秘设定，都打不了单词了
https://github.com/alex-shpak/hugo-book/issues/134
能提个建议吗， 代码可不可以贴全， 有的函数没有贴上去，想运行一下看看效果还要重写缺失的函数， 挺蛋疼的， 这个题好像没有max函数？
@whl5627445 你这个建议很好。代码并不是我故意不贴全。是因为我把所有题的代码放在一个包里面了。一个包里面的函数只能唯一。如果每道题都要写 max 函数，那么就需要写 max_XXXX （带题号）变成不同的函数。我目前还没有这样做。
@whl5627445 能提个建议吗， 代码可不可以贴全， 有的函数没有贴上去，想运行一下看看效果还要重写缺失的函数， 挺蛋疼的， 这个题好像没有max函数？
函数很简单。可以自己写一下。
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
}
if (len(nums1)+len(nums2))&1 == 1 { return float64(midLeft) } 请问一下这个代码是什么含义
