E1920.基于排列构建数组

math, https://leetcode.cn/problems/build-array-from-permutation/

给你一个 从 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 也包含在内）的不同整数组成的数组。

示例 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]

提示：

1 <= nums.length <= 1000
0 <= nums[i] < nums.length
nums 中的元素 互不相同

进阶：你能在不使用额外空间的情况下解决此问题吗（即 O(1) 内存）？

✅ 解法一：直接构造（简单易懂）

直接遍历数组，对每个位置 i，取 nums[i] 作为下标再次查找，得到 nums[nums[i]]，然后放入结果数组中。

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

python

from typing import List

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        return [nums[nums[i]] for i in range(len(nums))]

✅ 解法二：原地修改（进阶问题：O(1) 额外空间）

如果题目要求 不使用额外空间，那么我们需要想办法把结果保存在原数组中。可以利用数学方法将新值和旧值存储在一个数中，最后再还原出来。

原理：

因为 nums[i] < 1000（根据提示），我们可以使用一个大于 1001 的基数（比如 1001）来编码两个值到一个整数中：

text

nums[i] = nums[i] + (nums[nums[i]] % 1001) * 1001

之后再解码：

text

nums[i] = nums[i] // 1001

这样我们就实现了 原地修改，没有使用额外空间。

代码如下：

python

from typing import List

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        
        # 第一步：将 nums[i] 编码为 nums[i] + nums[nums[i]] * n
        for i in range(n):
            # 使用 nums[nums[i]] 的原始值，需要取模
            val = nums[nums[i]]  # 先取出要用的值
            nums[i] = nums[i] + (val % n) * n  # 防止重复编码
        
        # 第二步：解码，得到最终结果
        for i in range(n):
            nums[i] = nums[i] // n
        
        return nums

🔍 注意：这里我们用到了 n 作为基数，是因为 nums[i] < n，所以 nums[i] * n + nums[nums[i]] 能够唯一表示两个值。

📌 关键点解释：

```
val = nums[nums[i]]
```
- 这里我们是想拿到原始数组中 nums[nums[i]] 的值。
- 但由于 nums[i] 可能已经被修改过，所以我们需要每次使用 val % n 来获取原始值。
在最后通过 / n 得到新的值，实现原地替换。

总结：

方法	时间复杂度	空间复杂度	是否原地
直接构造	O(n)	O(n)	❌
原地修改	O(n)	O(1)	✅

E1920.基于排列构建数组 ​

E1920.基于排列构建数组