已知两个长度分别为 m 和 n 的升序链表,若将它们合并为一个长度为 m+n 的降序链表,则最坏情况下的时间复杂度是()
A. O(n)
B. O(m * n)
C. O(min(m, n))
D. O(max(m, n))
N诺智能批改可自动批改答案并给出反馈,每次使用将消耗 1个诺币
您当前的诺币数量: 个
N诺正在智能批改,预计需要30秒,请稍候...
头插法,不需要管他是不是升降。
最少次数的比较:走完短的链表发现短链表的最小值还是比长链表最大值大;这种种情况下的比较次数是n次,复杂度为:O(min(m,n)); 最大次数的比较:那当然是一步一比较,两链表的值是穿插着的就好比value值分别为:1 3 5 7和2 4 6 8 10的两个链表,可以多带入点值发现此种情况下的比较次数为n+m-1(一步一比较的情况下剩下的最后一个值不用比较直接链上就对了);所以说时间复杂度为O(N+M-1),最高次都是一次,选择的时候应该选择最大的那个数了,道理跟O(n+10000)为O(n)是一样的,所以答案是D为:O(MAX(M,N))
最小值的话,答案不该是C吗?
参考答案:D
答案解析:m、...
登录后提交答案