1920. 基于排列构建数组

🟢   🔖  数组 模拟  🔗 力扣 LeetCode

题目

Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.

A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).

Example 1:

Input: nums = [0,2,1,5,3,4]

Output: [0,1,2,4,5,3]

Explanation: The array ans is built as follows:

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]

Example 2:

Input: nums = [5,0,1,2,3,4]

Output: [4,5,0,1,2,3]

Explanation: The array ans is built as follows:

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]

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] < nums.length
• The elements in nums are distinct.

Follow-up: Can you solve it without using an extra space (i.e., O(1) memory)?

题目大意

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

解题思路

为了在原数组中保存额外的信息，可以采用编码技巧，将两个值（当前值和新值）存储在一个数中，利用数组长度 n 来区分这两个值。

1. 编码技巧：

   • 对于数组中的每个元素 nums[i]：
     • 当前值（cur）：原本的 nums[i]。
     • 新值（target）：nums[nums[i]] 的值。
   • 将 nums[i] 替换为 target * n + cur，同时保留了原值和新值。

2. 解码：

   • 通过取模操作 (nums[i] % n) 获得原值 cur。
   • 通过整除操作 (Math.floor(nums[i] / n)) 获得新值 target。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度，遍历数组两次：一次编码，一次解码。
• 空间复杂度：O(1)，不使用额外数组。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var buildArray = function (nums) {
	const n = nums.length;

	for (let i = 0; i < n; i++) {
		let cur = nums[i];
		let target = nums[nums[i]] % n;
		nums[i] = target * n + cur;
	}

	return nums.map((i) => Math.floor(i / n));
};