将两个数组合并在一起

Question

如果A1 = {10, 20, 30, 40, 50, 60}和A2 = {15, 25, 35, 45}是两个数组，合并两个数组所需的比较次数是多少？

我在solvng这个问题的看法是

合并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个比较就足够了。 但事实并非如此。

你说什么？

Answer 1

这就像两行人，你是银行出纳员。只要在各自线路前面有两个人，就必须比较它们以决定采取哪一种。在一行为空之后，您可以将其他行中的所有剩余人员无需进行比较。 （这个比喻假设输入是链表，如果你合并阵列，那么必须复制另一行的尾部，答案是不同的。）

考虑到所有这些，不难看出比较次数取决于你正在合并的值。至少它是min（m，n），其中m和n是输入的长度。最大值为m + n - 1.

Answer 2

您不会比较（每次）数组中的元素（从0开始）。在合并两个数组时，您会使用额外的数组来保存元素，因为它们是排序和合并。

在你的情况，你保留第三个数组 - B其中B.length = A1.length+A2.length。

阵列的合并和相应的数量比较像以下内容： -

A1[0]<A2[0] --> B[0] = A1[0] 
A1[1]>A2[0] --> B[1] = A2[0] // total number of comparisons is 2 

A1[1]<A2[1] --> B[2] = A1[1] 
A1[2]>A2[1] --> B[3] = A2[1] // total number of comparisons is 4 

A1[2]<A2[2] --> B[4] = A1[2] 
A1[3]>A2[2] --> B[5] = A2[2] //total number of comparisons is 6 

A1[3]<A2[3] --> B[6] = A1[3] 
A1[4]>A2[3] --> B[7] = A2[3] //total number of comparisons is 8 

在此之后，没有留下B.元素。因此，我们复制B.

剩余的元素所得阵列如下： -

B = {10,15,20,25,30,35,40,45,50,60}

所以，比较的总数是8而不是20