1920. 基于排列构建数组

题目链接

1920. 基于排列构建数组 - 力扣（LeetCode）

题目描述

给你一个 从 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，需要构建一个新数组ans，其中ans[i] = nums[nums[i]]。
   • 要求：不使用额外空间（即原地修改nums），且时间复杂度为O(n)。
2. 关键思路：
   • 原地置换：利用数组本身存储信息，同时标记已处理的位置。
   • 标记方法：通过取反（~）操作标记已处理的位置（题目保证nums[i]是非负的，取反后变为负数）。
   • 置换链：每个元素nums[i]指向的位置构成一个置换链，需要沿着链处理，直到闭环。
3. 步骤分解：
   • 第一遍遍历：
     • 对每个未处理的元素（nums[i] >= 0），沿着nums[i] -> nums[nums[i]] -> ...的链处理。
     • 将链上的值依次取反后存入前一个位置（标记为已处理）。
     • 闭环后，将起始值取反存入最后一个位置。
   • 第二遍遍历：
     • 将所有取反的值恢复（~nums[i]）。
4. 举例说明：
   • 输入：nums = [0,2,1,5,3,4]
   • 第一遍遍历：
     • i=0：链0 -> 0，直接标记nums[0] = ~0 = -1。
     • i=1：链1 -> 2 -> 1，依次处理：
       • nums[1] = ~nums[2] = ~1 = -2
       • nums[2] = ~nums[1]（原值已更新为-2，实际是~2 = -3）
       • 闭环后nums[2] = ~2 = -3。
     • 类似处理其他位置。
   • 第二遍遍历：将所有负数取反恢复为正数。

题解代码

classSolution{publicint[]buildArray(int[]nums){// 第一遍遍历：原地置换并标记for(inti=0;i<nums.length;i++){intx=nums[i];// 当前元素的值if(x<0){// 如果已经处理过（被标记为负数），跳过continue;}intcur=i;// 当前索引// 循环处理当前置换链while(nums[cur]!=i){// 直到找到闭环（nums[cur] == i）intnxt=nums[cur];// 下一个要处理的位置nums[cur]=~nums[nxt];// 将下一个位置的值取反后存入当前位置（标记为已处理）cur=nxt;// 移动到下一个位置}nums[cur]=~x;// 闭环后，将起始值取反存入最后一个位置}// 第二遍遍历：恢复原始值（去掉标记）for(inti=0;i<nums.length;i++){nums[i]=~nums[i];// 取反恢复原始值}returnnums;}}

复杂度分析

1. 时间复杂度：
   • 每个元素最多被处理两次（标记和恢复），因此时间复杂度为O(n)。
2. 空间复杂度：
   • 仅使用常数额外空间（如临时变量x、cur、nxt），因此空间复杂度为O(1)。