How can I solve the Build Array from Permutation problem efficiently?

You can solve it efficiently by directly simulating the array mapping described in the problem statement, iterating over the array in linear time.

What is the time complexity of this problem?

The time complexity is O(n) because we loop through the input array once to build the result array.

How do I meet the O(1) space complexity requirement?

You can meet the O(1) space complexity requirement by modifying the array in place or using minimal extra space, like a temporary variable.

What happens if I use extra space for the result array?

Using extra space would violate the problem’s constraints, and you would lose points for not adhering to the O(1) space requirement.

How can I handle edge cases in this problem?

You should test the solution with small arrays (such as length 1) and very large arrays to ensure the solution works across all possible input sizes.

#1920

Easy

auto_awesome数组·模拟

LeetCode 题解工作台

基于排列构建数组

给你一个从 0 开始的排列 nums （下标也从 0 开始）。请你构建一个同样长度的数组 ans ，其中，对于每个 i （ 0 ），都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans 。从 0 开始的排列 nums 是一个由 0 到 nums.length …

数组模拟

题目描述

给你一个 从 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) 内存）？

lightbulb

解题思路

方法一：模拟

我们可以直接模拟题目描述的过程，构建一个新的数组 $\textit{ans}$ ，对于每个 $i$ ，令 $\textit{ans}[i] = \textit{nums}[\textit{nums}[i]]$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate directly simulate the process described in the statement?
question_mark
Does the candidate maintain O(1) space complexity in their solution?
question_mark
Does the candidate handle edge cases and large input sizes correctly?

warning

常见陷阱

外企场景

error
Confusing the problem with a more complex array manipulation task, forgetting to follow the direct simulation approach.
error
Using extra space beyond O(1), which violates the problem’s constraints on space efficiency.
error
Overlooking edge cases such as very small or very large arrays, causing the solution to fail in certain scenarios.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to handle multi-dimensional arrays.
arrow_right_alt
Consider implementing a more complex simulation with different mapping rules.
arrow_right_alt
Increase the size of the array significantly, ensuring the solution scales efficiently.

help

常见问题

外企场景

继续练习

#1914 循环轮转矩阵 #1929 数组串联 #1894 找到需要补充粉笔的学生编号