首页 > 试题广场 >

将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是

[单选题]
将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是() 
  • 2n
  • 2n-1
  • n-1
  • n
查看正确选项
添加回答
Gotchaha头像 Gotchaha
最少不应该是N/2吗
发表于 2021-04-22 13:51:01 回复(0)
想做樱木的圆寸少年头像 想做樱木的圆寸少年
我理解的最少的比较次数是当一个有序表A的所有元素都大于另一个有序表B的所有元素时。

当A表中的第一个元素与B表中的所有元素比较一次，并发现该元素大于B表中的最大元素时，

A表剩下的所有元素都不需要再比较，直接依次添加在B表的末尾。

该过程一共比较了N次
发表于 2016-02-01 11:34:08 回复(7)
烟消bug云散头像 烟消bug云散
最小情况：把前一个表A中的第一个值与后一个表B相比较，发现最小的值比B的最大的值都要大，所以第一个回答中的次数其实不是1次，而是N次，因为你没办法直接访问到最后一个元素
发表于 2016-07-04 08:58:09 回复(2)
那结局呢头像 那结局呢
有没有可能是一次呢？其中一个表的最小元素大于另一个表的最小元素
发表于 2015-12-18 20:51:33 回复(12)
小道仙头像 小道仙
最好的情况两个数组为
[1,2,3]   [4,5,6]
1 2 3 依次和4比较然后结束
发表于 2019-10-05 14:38:07 回复(0)
达芬奇伯爵头像 达芬奇伯爵
说了是归并排序，有两个指针分别指向两个有序表的表头，依次比较直到一个表完，那最少比较次数就是小一些的表的大小，两个表都是n，那么次数自然是n次
发表于 2016-06-26 14:12:53 回复(0)
dher头像 dher
这里所说的最少次数是基于归并排序的基础上，归并排序的过程是依次取两个表中的最小元素进行比较，然后较小的则放入新表，所以最少次数应为n。像有些人所说的先拿一个表最小的和另一个表最大的去比较则是一种投机取巧的做法，其实际整体效率远低于归并算法，实际应用中一般不会这样比较，况且题干中已经说了是用归并排序。
发表于 2020-06-12 16:22:08 回复(0)
尐短腿头像 尐短腿
最少一次啊 感觉！！
发表于 2016-06-13 11:41:57 回复(0)
白雪少年头像 白雪少年
两个表都只有一个元素，比较一次就行了
发表于 2018-08-05 23:18:54 回复(0)
爱上_向日葵的执着头像 爱上_向日葵的执着
假设这两个数组为A[0....n-1] ，B[0....n-1]且A中值均比B中值小，那么比较的顺序应该
A[0]<B[0],A[1]<B[0],A[2]<B[0].......,A[n-1]<B[0],所以比较的次数应该是n次
编辑于 2018-03-22 17:02:21 回复(0)
風吹鸡蛋壳头像 風吹鸡蛋壳
时间复杂度是不是应该是2n?
发表于 2017-03-06 15:20:43 回复(0)
Gerhold头像 Gerhold
为什么是n
发表于 2016-08-04 09:52:00 回复(0)
codersong头像 codersong
最少比较次数的情况是其中一个表的元素均小于另一个表中的元素，最小比较次数为n。
发表于 2016-03-01 10:14:11 回复(0)
提交观点

问题信息

排序
来自：迅雷2016研发工程师笔试题
上传者：SunburstRun
难度：
13条回答 16771浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号