gpt4 book ai didi

algorithm - 从源排列到目的地的最小移动数

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

给定 [1...N] 的排列“S”和一个空闲点,因此序列的总长度为 N+1。

只需一步,您就可以将排列中的任何元素与空闲点交换。

您需要找到从“S”到排序的排列序列的最小步数。

最佳答案

如果我理解正确,huck_cussler 的解决方案需要前瞻性搜索应该位于空白处的数字位置。

这里有一个替代解决方案,它不需要前瞻,最多使用 2N 次交换。

static void swapperSort(int[] arr)
{
int n = arr.length-1;
for(int i=0, pos=0, space=n; i<n-1;)
{
System.out.print(pos + " " + space + " " + Arrays.toString(arr));
if(arr[pos] == pos+1)
{
pos = ++i;
}
else
{
System.out.print(" SWAP");
int idx = arr[pos]-1;
swap(arr, idx, space);
swap(arr, pos, idx);

int tmp = space;
space = pos;
pos = tmp;
}
System.out.println();
}
System.out.println(Arrays.toString(arr));
}

这是 DAle 测试用例的输出:

0 6 [2, 1, 4, 3, 6, 5, 0] SWAP
6 0 [0, 2, 4, 3, 6, 5, 1] SWAP
0 6 [1, 2, 4, 3, 6, 5, 0]
1 6 [1, 2, 4, 3, 6, 5, 0]
2 6 [1, 2, 4, 3, 6, 5, 0] SWAP
6 2 [1, 2, 0, 4, 6, 5, 3] SWAP
2 6 [1, 2, 3, 4, 6, 5, 0]
3 6 [1, 2, 3, 4, 6, 5, 0]
4 6 [1, 2, 3, 4, 6, 5, 0] SWAP
6 4 [1, 2, 3, 4, 0, 6, 5] SWAP
4 6 [1, 2, 3, 4, 5, 6, 0]
[1, 2, 3, 4, 5, 6, 0]

关于algorithm - 从源排列到目的地的最小移动数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45286653/

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