java - 在 O(N) 时间内对数组进行排序

Question

给定一个包含整数 1,2,3,...,N 和字符 ""(空格)的数组 A 我们想将它排序为 [1,2,3,...,N,""]，我们只能用 ""交换整数，但不能互相交换，所以 swap(3,"") 是允许的，而 swap(1,2) 是不允许的。

我的尝试是将空间表示为 "-1"，并在 O(N) 时间内搜索它，然后从 i=1< 再次遍历数组 到 N+1，如果我看到例如 A[2] = 7，我会将 A[7] 换成 ""，然后我会用 "" 交换 A[2]，同时跟踪 "" position 因为这是交换的唯一方法，这样 7 将以 A[7] 结束(索引移位除外) 我写的代码如下:

public static int[] arraySort(int[] array){

    int space = 0;

    for(int i = 0; i<array.length; i++ ){
        if(array[i] == -1){
            space = i;
        }
    }

    for(int i = 0; i<array.length; i++){
        if(array[i] != i+1 && array[i] !=-1){
            swap(array, array[i]-1 , space);
            space = array[i]-1;
            swap(array, i, space);
            space = i;
        }
    }
    return array;
}

public static void swap(int[] arr, int ind1, int ind2){

    int temp = arr[ind2];
    arr[ind2] = arr[ind1];
    arr[ind1] = temp;
}

它确实有效，但是对于 A[7,3,5,4,6,1,2,-1] 这样的输入 它失败了，我知道我可能会向数组的头部发送一个整数，但我不明白为什么它不会返回，因为那里有一个不同的数字，然后它最终会到达它的位置。 帮助？或如何解决此问题的想法(同时尽可能将其保持在 O(N) 时间内？

Answer 1

您描述的算法非常正确，但您犯了一些错误。

首先，您可能必须在同一个位置交换多次。其次，如果你击中了空间，你必须把它放在正确的位置。这是你的循环固定。请注意，我提前一个位置停止了迭代。

for(int i = 0; i<array.length-1; i++){
    while (array[i] != i+1){
        if (space==i) {
            // it's the space
            swap(array, i, array.length-1);
            space = array.length-1;
        } else {
            swap(array, array[i]-1, space);
            space = array[i]-1;
            swap(array, space, i);
            space = i;
        }
    }
}

请注意，在我们移动一个数字后，我们总是以 space = i 结束，所以我们将在下一次内部迭代中处理空间。我们可以优化它，最终得到看起来像@OmG 的方法，除了他也错过了 while 循环:

swap(array, space, array.length-1);

for(int i = 0; i<array.length-1; i++){
    while (array[i] != i+1){
        int currentTarget = array[i]-1;
        //move space to current target
        swap(array, currentTarget, array.length-1);
        //move current element to its target
        swap(array, currentTarget, i);
        //put the space back where it belongs
        swap(array, i, array.length-1);
    }
}

重要的是要理解为什么这仍然是 O(n)，即使我们已经添加了一个内循环:内循环的每次迭代都固定了一个数字的位置，之后我们永远不会再移动那个号码。这最多可能发生 n 次，因为只有那么多数字需要修正。