在 O(1) space 中就地合并两个排序数组

Question

谁能帮我理解这个问题的算法/代码

给定两个整数数组，对它们进行排序，将初始数字放在第一个数组中，将剩余数字放在第二个数组中。例如：

Input: ar1[ ] = {1, 5, 9, 10, 15, 20}

        ar2[] = {2, 3, 8, 13}

Output: ar1[ ] = {1, 2, 3, 5, 8, 9}

         ar2[] = {10, 13, 15, 20}

代码：

    void merge(int ar1[], int ar2[], int m, int n)
{
    // Iterate through all elements of ar2[] starting from
    // the last element
    for (int i=n-1; i>=0; i--)
    {
        //Find the smallest element greater than ar2[i]. Move all
        //   elements one position ahead till the smallest greater
        //   element is not found
        int j, last = ar1[m-1];
        for (j=m-1; j >= 0 && ar1[j] > ar2[i]; j--)
            ar1[j+1] = ar1[j];

        // If there was a greater element
        if (j != m-1)
        {
            ar1[j+1] = ar2[i];
            ar2[i] = last;
        }
    }
}

我在这个网站上看到了这个解决方案：http://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-space/

Answer 1

直觉

对于 ar2 的每个元素 ar2[i]（即在外循环内）基本上您可以在 ar1 中找到索引 j 这样 [= 的所有元素范围 [(j+1), (m-1)] 中的 13=] 大于 ar2[i]。然后你取那个范围内的最小元素，然后 把它从 ar1 到 ar2 的 扔掉，特别是索引为 i 的单元格，其中ar2[i] 中的值在被转移到 ar1.

之前曾经驻留过

将 ar2[i] 转移到 ar1[j+1] 的原因是为了在 ar1 中收集最小的 m 个元素，在 ar2 中收集其余元素。这个算法所做的可以说是优雅的事情是从右到左遍历 ar2。如果您还记得 ar1 和 ar2 都是排序的，那么 ar2 从右到左的内容有助于实现 使用常量额外 space 如下

当您在 ar2 上从右向左移动时，您会遇到 ar2[i] 中的值减少或至少不增加的情况。这意味着您会发现 ar1[m-1] 的递减值或非递增值可以替换它们。基本上，大于 ar2[i] 的最小元素 ar1[m-1] 将不会随着值 ar2[i] 的增加而随着我们从右向左移动而减少。

因此，我们在外层循环的每一次迭代中丢掉ar1到arr2的元素也会是非升序或降序，我们将它们按降序放置到索引中, 保持 ar2 有序。

不变方法

一个可能但相当非正式的不变是 ar1 和 ar2 将在每次迭代后排序，最多有一个元素 ar2，比如 ar2[i]，其中至少存在 1 个 ar1[k]>ar2[i] 与 ar1 中的元素交换，其方式不违反任一数组的排序顺序。

最初元素是有序的。每次迭代后，如果 ar1 中索引 j 中存在小于 ar2[i] 的元素，则所有大于 ar2[i] 的范围向右移动 1。 ar2[i] 放在 ar1[j+1] 中，这样就不会违反 ar1 的顺序。然后，ar1 的 之前最后一个 元素不再适合 ar1，被放入 ar2[i].

很容易看出，ar1 的顺序在外循环的每次迭代中都保持不变。 ar2 的顺序需要更多的注意力。

每次我们将 ar2 的元素放入 ar1 时，我们知道之前 ar1 的最后一个元素我们将放入 ar2 （即在适当的位置ar2[i]) 已知大于 ar2[i]，因为它大于或等于 ar1[j+1]，后者大于 ar2[i]。 (ar2[i] < ar1[j+1] <= last)

此外，ar2 中任何先前被替换的元素（即 ar2 的第 i 个索引右侧的元素）已被替换为值 last 大于或等于当前迭代中的最后一个值，因为 ar1 最初是订购的。

因此每次迭代后，ar2也保持有序，算法终止后，不存在元素ar2[i]，因此存在元素ar1[k] > ar2[i].

Answer 2

import java.util.Arrays;

public class MergeArray {

    public static void mergeArray(int[] input1, int[] input2) {

        Arrays.sort(input1);

        for(int i = 0; i < input1.length; i++) {
            for(int j = 0; j < input2.length; j++) {
                if (input1[i] < input2[j]) {
                    continue;
                } else {
                    int temp = input1[i];
                    input1[i]=input2[j];
                    input2[j]=temp;
                }
            }
        }

        for(int i =0 ; i < input1.length; i++) {
            System.out.println(input1[i]);
        }
        Arrays.sort(input2);
        System.out.println("Array 2");
        for(int i = 0; i < input2.length; i++) {
            System.out.println(input2[i]);
        }
    }

    public static void main(String[] args) {
        int[] array1= {2,7} ;   
        int[] array2= {5,3,8,1} ;
        mergeArray(array1, array2);
    }
}

在 O(1) space 中就地合并两个排序数组

Merge two sorted arrays in place in O(1) space

arrays

sorting

in-place

直觉

不变方法