用最少的移动对数组进行排序

One Two Three 发表于 Dev

一二三

我遇到了这个问题：

有n + 1个装卸码头。将框1-> n的排列放在第一个n上。有一个叉子可以一次将一个盒子移到一个空的位置。给出一种算法，以最少的移动次数对箱子进行排序。

我的算法（伪代码）（从1开始的索引）

（0）将计数器设置为0
（1）遍历查找max框的数组。将其移至最后一个插槽（n + 1）。计数器加1。
（2）然后从头开始重新开始，直到limit = n_th个插槽，找到max框并将其交换到末尾。将计数器增加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;
        }

    }

有什么更好的算法呢？

索拉夫·萨胡（Saurav Sahu）

有一个很好的技术可以解决这个问题。可以说我们有这个顺序的盒子。

[5] 4 2 3 1

将第一个框与第5个框交换（这是第一个框的值）以获取：

[1] 4 2 3 5

现在，第一个盒子在正确的位置。移至第二。

1 [4] 2 3 5

将第二个盒子与第四个盒子交换（这是第二个盒子的值）以得到：

1 [3] 2 4 5

现在再次检查第二个框是否在正确的位置。用3rd（这是2nd box的值）交换2nd box以获得：

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

总共9步以O（n）的较低时间复杂度进行。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。