【数据结构】将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是？

Question

问题如题

答案是n，我的答案是1或者3，恳请大大答疑

先说下我的思路：

1. 既然要最少比较情况，那么考虑最好情况就行了，那么肯定表2最小的元素大于表1最大的元素，例如[1,2,3],[4,5,6]，只需要拿4和3做一次比较，就可以了，至于遍历，合并等操作的次数不在考虑范围内了
2. 如果是不确定是升序还是降序，那么表2和表2，0号元素和1号元素各比较一次，2次，再拿表1的最大值和表2的最小值做比较，1次，总共三次。

Answer 1

你这个比较，跟马后炮一样，你是知道了结果才得出的一次比较，说实话，照你这样弄，一次比较都不用，直接头尾相接就好了。