there is n+1 loading docks. a permutation of boxes 1->n is placed on
the first n. there is a fork that can move one box to an empty
location at a time. Give an algorithm to sort the boxes with minimum
number of moves.
我的算法(伪代码)(基于1的索引)
>(0)将计数器设置为0
>(1)遍历查找最大框的数组.将其移至最后一个插槽(n 1).递增计数器1.
>(2)然后从开始重新开始到limit = n_th slot,找到max box并将其交换到结尾.增加计数器3(因为交换需要3次移动).
>(3)将限制减少1
>回到(2)直到极限达到1
更新：Saruva Sahu在下面提出了一个非常好的解决方案,我优化了一点以避免“交换”.
public static void moveToPos(int[] nums) {
int tempLoc = nums.length - 1;
final int n = nums.length - 2;
// boxes --> loc
Map<Integer, Integer> tracking = new HashMap<>();
for (int i = 0; i < n; ++i) {
// if the target place is empty
if (nums[i] == tempLoc) {
// then move it there
nums[tempLoc] = nums[i];
// new temp loc
tempLoc = i;
}
else if(nums[i] != i) {
// move current box at target out of the way
nums[tempLoc] = nums[nums[i]];
if (tempLoc != nums[nums[i]]){
// nums[i] is not at the right place yet
// so keep track of it for later
tracking.put(nums[nums[i]], tempLoc);
}
nums[nums[i]] = nums[i];
tempLoc = i;
}
}
// move the unstelled to its right place
while (!tracking.isEmpty()) {
// where is the box that is supposed to be at tempLoc
int loc = tracking.remove(tempLoc);
nums[tempLoc] = nums[loc];
// make the emtpy spot the new temp loc
tempLoc = loc;
}
}
对此有什么更好的算法？
有一种非常好的技术可以解决这个问题.让我们说我们有这个顺序的盒子.[5] 4 2 3 1
用第5个交换第1个方框(这是第1个方框的值)得到：
[1] 4 2 3 5
现在第一个盒子在正确的位置.转到第二个.
1 [4] 2 3 5
用第4个交换第2个方框(这是第2个方框的值)得到：
1 [3] 2 4 5
现在再次检查第二个盒子是否处于正确位置.
交换第二个框与第三个(这是第二个框的值)得到：
1 [2] 3 4 5
现在再次检查第二个盒子是否处于正确位置.如果没有移动到下一个索引.
重复上述步骤直到第n个框.
1 2 [3] 4 5 1 2 3 [4] 5 1 2 3 4 [5]
而已.盒子将被分类.
重要注意事项：
>此算法仅适用于阵列中所有数字都是连续的情况(排序或未排序无关紧要).请求者在评论部分确认了此要求.
>在每次交换期间,您在其正确的最终位置放置至少一个框,这是该算法的最佳选择.在最好的情况下,您可以放置2个盒子
在第一次交换中发生的每次交换([5] 4 2 3 1 – > [1] 4 2 3 5).
>每个交换都需要一个空盒子/空间,可根据要求提供.
>每次交换(A和B之间)由3个移动组成.将A移动到空白区域,然后将B移动到A的位置,然后将A移回B的旧位置.因此,A保证获得正确的最终位置.
更新：
Nico建议的算法给出了最小移动次数,如下所示：
5 4 2 3 1 [ ] : Start positions .. 4 2 3 1 [5] : 1st move 1 4 2 3 .. [5] : 2nd move 1 4 2 3 5 [ ] : 3rd move 1 .. 2 3 5 [4] : 4th move 1 2 .. 3 5 [4] : 5th move 1 2 3 .. 5 [4] : 6th move 1 2 3 4 5 [ ] : 7th move
共计7次移动的代价是时间复杂度较高的O(n ^ 2).
另一方面,我建议的算法保证最低时间复杂度O(n),但不是最小移动次数,如下所示：
[5] 4 2 3 1 -> [1] 4 2 3 5 : 3 moves to swap 5 and 1 1 [4] 2 3 5 -> 1 [3] 2 4 5 : 3 moves to swap 4 and 3 1 [3] 2 4 5 -> 1 [2] 3 4 5 : 3 moves to swap 3 and 2
在O(n)的较低时间复杂度下总共9次移动.