1920. 基于排列构建数组

1. 题目链接

1920. 基于排列构建数组 - 力扣（LeetCode）

2. 题目描述

给你一个 从 0 开始的排列 nums（下标也从 0 开始）。请你构建一个 同样长度 的数组 ans ，其中，对于每个 i（0 <= i < nums.length），都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans 。

从 0 开始的排列 nums 是一个由 0 到 nums.length - 1（0 和 nums.length - 1 也包含在内）的不同整数组成的数组。

3. 题目示例

示例 1 :

输入：nums = [0,2,1,5,3,4]
输出：[0,1,2,4,5,3]
解释：数组 ans 构建如下：
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
    = [0,1,2,4,5,3]

示例 2 :

输入：nums = [5,0,1,2,3,4]
输出：[4,5,0,1,2,3]
解释：数组 ans 构建如下：
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
    = [4,5,0,1,2,3]

4. 解题思路

1. 问题理解：
   • 给定一个数组 nums，需要构建一个新数组 ans，其中 ans[i] = nums[nums[i]]。
   • 要求：不使用额外空间（即原地修改 nums），且时间复杂度为 O(n)。
2. 关键思路：
   • 原地置换：利用数组本身存储信息，同时标记已处理的位置。
   • 标记方法：通过取反（~）操作标记已处理的位置（题目保证 nums[i] 是非负的，取反后变为负数）。
   • 置换链：每个元素 nums[i] 指向的位置构成一个置换链，需要沿着链处理，直到闭环。
3. 步骤分解：
   • 第一遍遍历：
     • 对每个未处理的元素（nums[i] >= 0），沿着 nums[i] -> nums[nums[i]] -> ... 的链处理。
     • 将链上的值依次取反后存入前一个位置（标记为已处理）。
     • 闭环后，将起始值取反存入最后一个位置。
   • 第二遍遍历：
     • 将所有取反的值恢复（~nums[i]）。
4. 举例说明：
   • 输入：nums = [0,2,1,5,3,4]
   • 第一遍遍历：
     • i=0：链 0 -> 0，直接标记 nums[0] = ~0 = -1。
     • i=1：链 1 -> 2 -> 1，依次处理：
       • nums[1] = ~nums[2] = ~1 = -2
       • nums[2] = ~nums[1]（原值已更新为 -2，实际是 ~2 = -3）
       • 闭环后 nums[2] = ~2 = -3。
     • 类似处理其他位置。
   • 第二遍遍历：将所有负数取反恢复为正数。

5. 题解代码

class Solution {
    public int[] buildArray(int[] nums) {
        // 第一遍遍历：原地置换并标记
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i]; // 当前元素的值
            if (x < 0) { // 如果已经处理过（被标记为负数），跳过
                continue;
            }
            int cur = i; // 当前索引
            // 循环处理当前置换链
            while (nums[cur] != i) { // 直到找到闭环（nums[cur] == i）
                int nxt = nums[cur]; // 下一个要处理的位置
                nums[cur] = ~nums[nxt]; // 将下一个位置的值取反后存入当前位置（标记为已处理）
                cur = nxt; // 移动到下一个位置
            }
            nums[cur] = ~x; // 闭环后，将起始值取反存入最后一个位置
        }

        // 第二遍遍历：恢复原始值（去掉标记）
        for (int i = 0; i < nums.length; i++) {
            nums[i] = ~nums[i]; // 取反恢复原始值
        }
        return nums;
    }
}

6. 复杂度分析

1. 时间复杂度：
   • 每个元素最多被处理两次（标记和恢复），因此时间复杂度为 O(n)。
2. 空间复杂度：
   • 仅使用常数额外空间（如临时变量 x、cur、nxt），因此空间复杂度为 O(1)。