题目简述

给定一个 从 0 开始的排列数组 nums，我们需要构造一个新数组 ans，其中每个元素满足：

ans[i] = nums[nums[i]]

约束条件：

• nums.length 在 [1, 1000] 范围内；

• nums[i] 的值在 [0, nums.length - 1]；

• nums 中元素互不相同（即是一个排列）；

解法一：直接构建（简单）

新建一个数组 ans，直接按照题目定义去赋值。

for (int i = 0; i < n; ++i) {
    ans[i] = nums[nums[i]];
}

时间复杂度：O(n) 空间复杂度：O(n)（因为用了新数组）

这个方法非常直接，但不是“空间最优”。

解法二：原地构造（空间 O(1)）

核心思想

把「当前值」和「目标值」合并编码进一个数字中，等到第二轮遍历时再解码。

思路分析：

• 由于 nums[i] 的范围是 [0, n-1]，我们可以用一个“进制”的方式，把两个值存进一个整数。

• 举个例子：

  • 用 nums[i] % B 表示「当前值」；

  • 用 nums[i] / B 表示「最终值」；

  • 合并公式：nums[i] += B * (nums[nums[i]] % B)

  其中 B 是一个大于 nums[i] 的整数（只要保证不冲突就行）。

Java 实现代码：

class Solution {
    public int[] buildArray(int[] nums) {
        int n = nums.length;
        int B = 1000;  // 只要大于最大值即可，这里因为题目限制最大是999，故选1000
​
        // 第一次遍历：混合编码
        for (int i = 0; i < n; ++i) {
            nums[i] += B * (nums[nums[i]] % B);
        }
​
        // 第二次遍历：还原最终值
        for (int i = 0; i < n; ++i) {
            nums[i] /= B;
        }
​
        return nums;
    }
}

时间复杂度：O(n) 空间复杂度：O(1)

延伸思考：这个技巧还适用于什么场景？

这种方法本质上是 原地双写值 + 商余编码技巧。它可以广泛用于：

• 原地数组重排（如：置换数组、状态标记）

• 记录两个状态（比如原状态和更新状态）

• 减少空间复杂度为 O(1) 的问题中

如果题目没有 1000 限制还能用吗？

可以！关键是要找到一个 大于最大元素值的基数 B，不一定非得是 1000。例如：

int max = Arrays.stream(nums).max().getAsInt();
int B = max + 1;

只要你确定 B > max(nums[i])，编码就不会冲突，方法依然适用。

总结我的解题过程：

• 起初用的最直接方法，空间 O(n)，一遍写完。

• 看到“进阶要求空间 O(1)”后，阅读官方题解。

• 初次看到「除法编码」思路觉得巧妙，但有点难懂。

• 认真理解后意识到：这是在用整数合并两份信息，典型的商余编码技巧。

• 探索了它的适用条件——比如最大值、溢出等。

• 最终彻底掌握，并形成自己的总结！

心得体会

原地构造不是魔法，而是编码思想的变种应用。很多时候复杂的问题可以用“数学小技巧”优雅地解决，关键在于敢于尝试、深入理解原理。