java - 我的排序算法说：您的代码没有在时间限制内执行。如何解决这个问题呢

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;
}

标签： javaalgorithmsortingdata-structuresswap

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的排列。所有排列都可以使用循环符号表示为不相交循环的组合：例如，排列由循环组成，因为排列映射、、和。这是一个数学事实，长度为k的循环需要 ( k - 1) 交换到“执行”或“撤消”。因此，问题的答案可以找到为 (3 5 4 1 2(1 3 4)(2 5)1 → 33 → 44 → 12 → 55 → 2k - 1) 对于每个循环。

有一种简单的算法可以在线性时间内找到置换的循环，使用集合来跟踪哪些元素已经“使用”，以便迭代地找到第一个“未使用”值，这将是下一个“未使用”值的开始循环。或者，您可以将数组中的值更改为某个标记（例如 -1）以指示它们已被使用，无需辅助数据结构即可。