題目資訊

• 題目編號: 1920
• 題目連結: Build Array from Permutation
• 主題: Array, Simulation

題目敘述

給定一個從零開始的排列nums（0-索引），構建一個與之相同長度的數組ans，其中$ans[i] = nums[nums[i]]$對於每個$0 \leq i < nums.length$成立，並返回它。

一個從零開始的排列nums是一個從$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 \leq nums.length \leq 1000$
• $0 \leq nums[i] < nums.length$
• nums中的元素是不重複的。

後續挑戰: 你能在不使用額外空間的情況下解決這個問題嗎（即，$O(1)$內存）？

直覺

此問題涉及從一組整數排列中構造一個新的陣列。主要任務是利用陣列的每個索引來映射到同一陣列中的另一個索引，並在該映射索引中獲取值。這類問題需要理解陣列的排列特性，利用其基於零的索引編號，並使用指定的變換規則來形成一個新的陣列。

解法

為了解決這個問題，我們將充分利用輸入陣列 nums 的排列性質。由於 nums 是一個基於零的排列，每個元素 nums[i] 是一個範圍從 0 到 nums.length - 1 的不同整數。基於此特性，我們可以確保不會發生越界錯誤或重複項。

1. 初始化：首先，我們確定輸入陣列 nums 的長度。然後，我們初始化一個與之長度相同的空陣列 result 來儲存轉換後的值。

2. 變換規則：我們迭代陣列 nums 中的每個索引 i。對於每個索引 i，我們將 result[i] 設置為 nums[nums[i]]。此操作有效地使用當前元素 nums[i] 作為索引，從 nums 中獲取值，從而在 result 陣列中創建一個新序列。

3. 結果彙編：在透過所有索引填滿 result 陣列後，我們將 result 作為最終輸出返回。

此方法以 $O(n)$ 的時間複雜度轉換陣列，其中 $n$ 是陣列的長度，因為它需要單次遍歷陣列來計算結果。該演算法也使用 $O(n)$ 的空間來儲存結果陣列。基於限制條件，此方法高效且簡單，利用排列的特性進行轉換。

程式碼

C++

class Solution {
public:
    // 根據給定的排列規則構建重新排列的數組的函數
    vector<int> buildArray(vector<int>& nums) {
        int length = nums.size();  // 獲取數組 nums 的長度
        vector<int> result(length); // 以相同的長度初始化結果數組

        // 遍歷 nums 中的每個元素以構建結果數組
        for (int i = 0; i < length; i++) {
            result[i] = nums[nums[i]]; // 設置每個元素為 nums[nums[i]]
        }

        return result; // 返回構建的數組
    }
};

Python

class Solution:
    # 根據給定的排列規則構建一個重排列的數組的函數
    def buildArray(self, nums):
        length = len(nums)  # 獲取數組 nums 的長度
        result = [0] * length  # 初始化與 nums 長度相同的結果數組

        # 遍歷 nums 中的每個元素以構建結果數組
        for i in range(length):
            result[i] = nums[nums[i]]  # 將每個元素設置為 nums[nums[i]]

        return result  # 返回構建好的數組

複雜度分析

• 時間複雜度: $O(n)$

  給定函數的時間複雜度為 $O(n)$，其中 $n$ 是輸入陣列 nums 的長度。這是因為該函數遍歷陣列 nums 一次，為每個元素執行一個常數時間操作來填充結果陣列。

• 空間複雜度: $O(n)$

  空間複雜度為 $O(n)$，這是由於創建了與輸入陣列 nums 長度相同的 result 陣列。除了輸入和輸出陣列之外，沒有使用其他額外的空間。