基于排列构建数组

记牢这套两层取值:先用 nums[i] 拿到下标 j,再用 nums[j] 拿到真正要填的值。下面从第 0 位开始,一位一位地走。

先摆好战场。上面这一行是输入 nums,下标从 0 到 5,里面装的正是 0 到 5 这六个数,顺序被打乱了。右边这张表是要构建的 ans,现在每一格都写着问号,表示还没填。接下来的活儿就是从左到右,把 ans 的每一格按规则算出来。

先用第 0 位把套路演示一遍。紫色框住的是当前位 i 等于 0,我们要读 nums[0]。读出来的这个数会告诉我们下一步该跳到哪个下标去。绿色标出的就是那个跳过去的落点。心里有了这个两层跳的画面,后面每一位都是重复它。

来到第 0 位,紫色指针停在下标 0。第一层动作:读 nums[0],值是 0。注意这个 0 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 0 格去取真正的值。

第二层动作:拿着刚才的下标 0,跳到 nums 的第 0 格,绿色框就是落点。这一位有点特别,nums[0] 正好是 0,跳过去落在的还是它自己这一格。这一格里装的是 0,这才是要填进 ans[0] 的值。

把 0 写进 ans[0]。右边那张表第 0 行的问号,现在换成了 0,点亮了。整条链路串起来就是 ans[0] 等于 nums[nums[0]],等于 nums[0],等于 0。这一位搞定,指针往右挪一格。

来到第 1 位,紫色指针停在下标 1。第一层动作:读 nums[1],值是 2。注意这个 2 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 2 格去取真正的值。

第二层动作:拿着刚才的下标 2,跳到 nums 的第 2 格,绿色框就是落点。这一格里装的是 1,这才是要填进 ans[1] 的值。

把 1 写进 ans[1]。右边那张表第 1 行的问号,现在换成了 1,点亮了。整条链路串起来就是 ans[1] 等于 nums[nums[1]],等于 nums[2],等于 1。这一位搞定,指针往右挪一格。

来到第 2 位,紫色指针停在下标 2。第一层动作:读 nums[2],值是 1。注意这个 1 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 1 格去取真正的值。

第二层动作:拿着刚才的下标 1,跳到 nums 的第 1 格,绿色框就是落点。这一格里装的是 2,这才是要填进 ans[2] 的值。

把 2 写进 ans[2]。右边那张表第 2 行的问号,现在换成了 2,点亮了。整条链路串起来就是 ans[2] 等于 nums[nums[2]],等于 nums[1],等于 2。这一位搞定,指针往右挪一格。

来到第 3 位,紫色指针停在下标 3。第一层动作:读 nums[3],值是 5。注意这个 5 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 5 格去取真正的值。

第二层动作:拿着刚才的下标 5,跳到 nums 的第 5 格,绿色框就是落点。这一格里装的是 4,这才是要填进 ans[3] 的值。

把 4 写进 ans[3]。右边那张表第 3 行的问号,现在换成了 4,点亮了。整条链路串起来就是 ans[3] 等于 nums[nums[3]],等于 nums[5],等于 4。这一位搞定,指针往右挪一格。

来到第 4 位,紫色指针停在下标 4。第一层动作:读 nums[4],值是 3。注意这个 3 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 3 格去取真正的值。

第二层动作:拿着刚才的下标 3,跳到 nums 的第 3 格,绿色框就是落点。这一格里装的是 5,这才是要填进 ans[4] 的值。

把 5 写进 ans[4]。右边那张表第 4 行的问号,现在换成了 5,点亮了。整条链路串起来就是 ans[4] 等于 nums[nums[4]],等于 nums[3],等于 5。这一位搞定,指针往右挪一格。

来到第 5 位,紫色指针停在下标 5。第一层动作:读 nums[5],值是 4。注意这个 4 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 4 格去取真正的值。

第二层动作:拿着刚才的下标 4,跳到 nums 的第 4 格,绿色框就是落点。这一格里装的是 3,这才是要填进 ans[5] 的值。

把 3 写进 ans[5]。右边那张表第 5 行的问号,现在换成了 3,点亮了。整条链路串起来就是 ans[5] 等于 nums[nums[5]],等于 nums[4],等于 3。这一位搞定,指针往右挪一格。

六位全部走完,回放一遍。ans 从头到尾是 [ 0, 1, 2, 4, 5, 3 ]。每一位都靠同一招:先用 nums[i] 拿到一个下标,再用那个下标去 nums 里取一次值。整个过程只从左到右扫了一遍,没有回头。

再抽第 3 位复核一下,这一位跨度最大,最能说明问题。nums[3] 是 5,于是跳到下标 5,nums[5] 是 4,所以 ans[3] 等于 4。和题面里那串解释完全对得上。别的位你也可以照这个法子自己验一遍。

边界想清:单元素返回自身、两元素交换、整体位移的排列都按同一招逐位取值。

面试重点:朴素版 O(n) 空间最稳;进阶用同格编码加两遍法做到 O(1) 额外空间,取余是为了还原原值。