我的排序算法说：您的代码未在期限内执行。如何解决这个问题

Question

我设计了一种算法，可以用最少的交换次数对数组进行排序。该数组由从1到n的连续数字组成。当我运行该程序时，它提示“您的代码未在期限内执行”。如何解决此问题？

static int minimumSwaps(int[] arr) {
    int n = arr.length;
    int swap = 0;
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            if (arr[i] != (i + 1)) {
                int temp = arr[i];
                arr[i] = arr[temp - 1];
                arr[temp - 1] = temp;
                swap++;
            }
        }
    }
    return swap;
}

Answer 1

对于这样的竞争性编程问题，甚至在开始编写任何代码之前，您都应该考虑必须处理的输入大小以及算法需要多少时间复杂度。对于HackerRank，大小为n <= 10 ^ 5的输入通常意味着您的算法必须在O（n log n）时间运行，如果不是O（n）时间。 >

您编写的算法需要O（n

²）的时间，您可能在编写任何代码之前就已经得出了；它使用两个嵌套循环，每个循环迭代n次，因此迭代次数是n次n。这意味着对于HackerRank上大小为10 ^ 5的输入，此算法不可能足够快，并且您需要一种根本不同的算法。

因为您知道数组元素是从1到n

的数字，没有重复或缺少值，所以实际上可以在O（n）时间内解决此问题。诀窍是将输入数组视为数字1到n的permutation。可以使用cycle notation作为不连续循环的组成来表示所有置换：例如，由于置换图3 5 4 1 2，(1 3 4)(2 5)，1 → 3和[ C0]和3 → 4。这是一个数学事实，长度为[[k的周期需要（k-1）交换为“ do”或“ undo”。因此，对于每个循环，问题的答案可以为（k-1）的总和。[一种简单的算法可以找到线性时间排列的周期，使用一个集合来跟踪哪些元素已经被“使用”，以便迭代地找到第一个“未使用”的值，该值将是下一个周期。另外，您可以将数组中的值更改为一些标记（例如-1），以指示它们已被使用，而无需使用辅助数据结构。