点击获取AI摘要

1920. 基于排列构建数组 E

给你一个 从 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 中的元素 互不相同

问题分析

给定一个从 0 开始的排列 nums，要求构造数组 ans，使得

$\forall i,\quad ans[i] = nums[nums[i]]$

直接遍历一次即可，对于每个索引 i，直接取 nums[i] 作为中间索引，再取对应值即可。

算法思路

对数组线性扫描和索引映射

时间复杂度

时间复杂度： $O(n)$ ，其中 n = nums.length

空间复杂度： $O(n)$ ，用于新数组 ans

$O(1)$ 内存实现

在不使用额外数组的前提下，我们可以「在原地」把每个位置上同时存储旧值和新值，待全部计算完毕后再把新值“取出”

由于 nums 中的所有元素都满足 0 ≤ nums[i] < n，我们可以利用「除与余」操作把两个数编码到同一个整数里：

$\text{new\_val} = nums[nums[i]] \quad(\,<n)\quad,\quad \text{old\_val}=nums[i]\quad(\,<n)$

将它们合并：

$nums[i] \leftarrow \text{old\_val} + (\text{new\_val} \times n).$

此时：

nums[i] % n 恢复得到原来的 old_val；
nums[i] // n 则是我们期望的 new_val。

遍历一遍数组，对每个 i 执行上述编码；
再遍历一遍，对每个 i 做 nums[i] //= n，这样 nums 就被原地改写成了结果数组。

时间复杂度： $O(n)$ ，两次线性扫描；

空间复杂度： $O(1)$ 。

代码实现

class Solution:
    def buildArray(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = [0] * n
        for i in range(n):
            ans[i] = nums[nums[i]]
        return ans

无需额外空间实现

class Solution:
    def buildArray(self, nums: list[int]) -> list[int]:
        n = len(nums)
        # 第一次遍历：编码 old_val 和 new_val
        for i in range(n):
            old = nums[i]
            new = nums[old] % n       # 这里 %n 确保拿到原始值
            nums[i] = old + new * n
        # 第二次遍历：取出 new_val
        for i in range(n):
            nums[i] //= n
        return nums