search

halfrost / LeetCode-Go

✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% / LeetCode 题解
https://books.halfrost.com/leetcode
MIT License
32.99k stars 5.7k forks source link

0004 合并nums1, nums2时间复杂度不应该是O(m+n)？ #111

Closed hitzhangjie closed 3 years ago

hitzhangjie commented 3 years ago

书中提及说是O(max(m,n))，nums1、nums2都有序，但是不一定nums1中都小于或者大约nums2， 最坏情况下需要完全遍历nums1、nums2吧？那不是O(m+n)？

halfrost commented 3 years ago

@hitzhangjie 0004 是 Median of Two Sorted Arrays 这道题吧？我刚刚搜了一下，好像没找到你说的 O(max(m,n))，这道题的代码时间复杂度是 O(log min(m,n)))，

hitzhangjie commented 3 years ago

奥，我描述的不清楚，是这里 合并有序数组的操作是 O(max(n,m)) 的，这里的合并应该是O(m+n)？

halfrost commented 3 years ago

@hitzhangjie 看到了你说的地方了。你说的是对的。我修改过来了。感谢指出！