算法practice1

6次阅读

https://github.com/CyC2018/CS-Notes/blob/master/notes/3.%20%E6%95%B0%E7%BB%84%E4%B8%AD%E9%87%8D%E5%A4%8D%E7%9A%84%E6%95%B0%E5%AD%97.md

你给出的这段代码展示了一个非常经典的**原地置换（In-place Swap）**算法。这种技巧在处理“数组元素范围在 $0$ 到 $n-1$ 之间”的问题时非常高效。

下面为你详细拆解其时空复杂度的分析逻辑：

初看代码，你可能会发现一个 for 循环嵌套了一个 while 循环，直觉上容易误判为 $O(n^2)$ 。但实际上，它是 均摊 $O(n)$ 。

核心逻辑：每一次 swap 操作，都会把至少一个数字送到它“应该在”的位置（即 nums[i] == i）。
归位原则：一旦一个数字被送到了正确的位置，它在后续的遍历中就不会再被移动。
计数分析：虽然 while 循环可能在某一次执行中循环多次，但对于长度为 $n$ 的数组，最多只需要 $n-1$ 次交换，就能让所有数字各就各位（或者发现重复）。
结论：每个元素最多被访问和交换常数次，因此总的时间复杂度是 $O(n)$ 。

这个比较直观，但也是该算法的精妙之处。

原地操作：算法直接在输入的 nums 数组上进行交换和比较。
额外变量：除了循环变量 i 和交换时用到的临时变量 t，没有申请任何与输入规模 $n$ 相关的额外空间（如 HashSet 或临时数组）。
结论：空间复杂度为极优的 $O(1)$ 。

你提供的代码段中有一个小的逻辑冗余和错误，我帮你标注并优化了一下：

Java

public int duplicate(int[] nums) {
    if (nums == null || nums.length <= 1) return -1;

    for (int i = 0; i < nums.length; i++) {
        // while 循环保证将 nums[i] 换到它正确的位置上
        while (nums[i] != i) {
            // 如果要交换的目标位置已经有了正确的数，说明抓到重复的了！
            if (nums[i] == nums[nums[i]]) {
                return nums[i];
            }
            // 交换
            swap(nums, i, nums[i]);
        }
        // 注意：原代码这里多了一个 swap(nums, i, nums[i])，是不需要的
    }
    return -1;
}

死循环风险：原代码 while 块后的那个 swap 是多余的，且逻辑上容易让人困惑。
核心判断：if (nums[i] == nums[nums[i]]) 是灵魂。它的意思是：我手里抓着一个 $2$ ，我想把它放回“老家”（索引为 $2$ 的位置），结果发现“老家”已经住着一个 $2$ 了。嘿，这就是重复！