1920. 基于排列构建数组

Easy

题目描述

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

从 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，新数组中 ans[i] = nums[nums[i]]。

方法一：直接模拟（推荐）

最直观的方法是创建一个新数组，遍历原数组，按照公式 ans[i] = nums[nums[i]] 填充结果数组。这种方法简单直接，时间复杂度为 O(n)，空间复杂度为 O(n)。

方法二：原地修改

题目的进阶要求提到能否用 O(1) 空间解决。可以利用数学技巧，将两个信息编码在一个数字中：nums[i] = originalValue + newValue * n，其中 n 是数组长度。这样可以在原数组上直接修改，最后再解码得到结果。

由于方法一更容易理解且代码更简洁，这里重点展示方法一，方法二在实际应用中较少使用。

实现步骤：

1. 创建与原数组相同长度的结果数组
2. 遍历原数组，计算每个位置对应的新值
3. 返回结果数组

代码实现

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }
};

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

public class Solution {
    public int[] BuildArray(int[] nums) {
        int n = nums.Length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }
}

var buildArray = function(nums) {
    const n = nums.length;
    const ans = new Array(n);
    for (let i = 0; i < n; i++) {
        ans[i] = nums[nums[i]];
    }
    return ans;
};

复杂度分析