如果A1 = {10, 20, 30, 40, 50, 60}和A2 = {15, 25, 35, 45}是两个数组，则合并两个数组所需的比较次数是多少？
我对解决这个问题的看法是
合并15，2个比较就足够了，所以现在看起来像
A1 = {10, 15, 20, 30, 40, 50, 60}; A2 = {25, 35, 45}
合并25、4个比较就足够了，所以现在看起来像
A1 = {10, 15, 20, 25, 30, 40, 50, 60}; A2 = {35, 45}
合并35，则6个比较就足够了，所以现在看起来像
A1 = {10, 15, 20, 25, 30, 35, 40, 50, 60}; A2 = {45}
合并45、8个比较就足够了，所以现在看起来像
A1 = {10, 15, 20, 25, 30, 35, 40, 45, 50, 60}
因此，进行20次比较就足够了。但事实并非如此。
你怎么说 ？
就像两行人一样，您是银行出纳员。只要各行的开头有两个人，您就必须比较他们来决定采取哪一个。一行为空后，您可以附加另一行中的所有其余人员，而无需进行比较。（以此类推，假设输入是链接列表。如果要合并数组，则必须复制另一行的尾部，并且答案也不同。）
考虑到所有这些，不难看出比较次数取决于您合并的值。至少是min（m，n），其中m和n是输入的长度。最大值为m + n-1。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句