1920.基于排列构建数组

【LetMeFly】1920.基于排列构建数组

力扣题目链接：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) 内存）？

解题方法：模拟

创建一个长度和nums相等的数组，从$0$到$len(nums)-1$遍历，令$ans[i]$的值为$nums[nums[i]]$即可。

  • 时间复杂度$O(len(nums))$
  • 空间复杂度$O(1)$，力扣算法返回值不计入算法空间复杂度

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 * @Author: LetMeFly
 * @Date: 2025-05-06 21:30:01
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-06 21:32:46
 */
class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        vector<int> ans(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
'''
Author: LetMeFly
Date: 2025-05-06 21:30:01
LastEditors: LetMeFly.xyz
LastEditTime: 2025-05-06 21:34:14
'''
from typing import List

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

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * @Author: LetMeFly
 * @Date: 2025-05-06 21:30:01
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-06 21:37:52
 */
class Solution {
    public int[] buildArray(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }
}

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * @Author: LetMeFly
 * @Date: 2025-05-06 21:30:01
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-06 21:39:38
 */
package main

func buildArray(nums []int) []int {
    ans := make([]int, len(nums))
    for i := range nums {
        ans[i] = nums[nums[i]]
    }
    return ans
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源