gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:30:25 25 4
gpt4 key购买 nike

给定一个包含整数 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) 时间内?

最佳答案

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

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

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 次,因为只有那么多数字需要修正。

关于java - 在 O(N) 时间内对数组进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57656973/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com