題目資訊

• 題目編號: 2460
• 題目連結: Apply Operations to an Array
• 主題: Array, Two Pointers, Simulation

題目敘述

你有一個以0為起始索引的數組 nums，大小為 $n$，由非負整数组成。

你需要對這個數組進行 $n - 1$ 次操作，其中在第 $i$ 次操作（以0為起始索引）中，針對 nums 的第 $i$ 個元素進行以下操作：

• 如果 nums[i] == nums[i + 1]，則將 nums[i] 乘以 $2$，並將 nums[i + 1] 設為 $0$。否則，略過此次操作。

完成所有操作後，將所有的 $0$ 移動到數組的末尾。

• 例如，數組 [1,0,2,0,0,1] 在將所有的 $0$ 移動到末尾後，會變成 [1,2,1,0,0,0]。

返回結果數組。

注意，操作是依次應用的，而不是同時全部進行。

範例 1:

輸入: nums = [1,2,2,1,1,0]
輸出: [1,4,2,0,0,0]
解釋: 我們執行以下操作：
- i = 0: nums[0] 和 nums[1] 不相等，因此略過此操作。
- i = 1: nums[1] 和 nums[2] 相等，我們將 nums[1] 乘以 2，並將 nums[2] 變為 0。數組變為 [1,4,0,1,1,0]。
- i = 2: nums[2] 和 nums[3] 不相等，因此略過此操作。
- i = 3: nums[3] 和 nums[4] 相等，我們將 nums[3] 乘以 2，並將 nums[4] 變為 0。數組變為 [1,4,0,2,0,0]。
- i = 4: nums[4] 和 nums[5] 相等，我們將 nums[4] 乘以 2，並將 nums[5] 變為 0。數組變為 [1,4,0,2,0,0]。
接著，我們將 0 移動到末尾，得到數組 [1,4,2,0,0,0]。

範例 2:

輸入: nums = [0,1]
輸出: [1,0]
解釋: 無法進行任何操作，我們只將 0 移動到末尾。

約束條件:

• $2 \leq nums.length \leq 2000$
• $0 \leq nums[i] \leq 1000$

直覺

這個問題牽涉到處理一個非負整數的陣列，通過執行一系列的操作，並將其重新排序以將零移動到末尾。這些操作的需求是由一組關於相鄰元素相等的條件明確定義的。直覺上，此問題的解法是在原地以線性方式處理這個陣列，從而有效地管理空間。同時確保在緊接的順序中保持非零元素的順序，並按照問題規範執行操作。主要的挑戰在於正確地鏈接操作並有效地處理零的移動。

解法

此解法涉及遍歷陣列，同時維護兩個指標：一個是讀取指標用來遍歷每個元素，另一個是寫入指標用來在執行操作時更新陣列。具體方法可以描述如下：

1. 初始化指標：將 readIndex 和 writeIndex 都設置為陣列的開始。readIndex 將遍歷整個陣列，而 writeIndex 將用於原地修改陣列。

2. 遍歷陣列：

   • 使用 readIndex 從 0 到 n - 1（n 是 nums 的長度）遍歷陣列。

   • 如果 nums[readIndex] 是零，則跳到下一個元素，因為涉及零的操作是無關的，而且我們最終希望將零推到末尾。

   • 如果 nums[readIndex] 不是零：

     • 檢查 nums[readIndex] 是否等於 nums[readIndex + 1]（確保 readIndex + 1 在界限內）。如果它們相等，則執行操作，將 nums[readIndex] 乘 2，然後設置 nums[readIndex + 1] 為 0，並將結果移動到 nums[writeIndex]。同時增加 readIndex（以跳過已經被修改為 0 的下一個元素）和 writeIndex。

     • 如果它們不相等，只需將 nums[readIndex] 複製到 nums[writeIndex]，然後增加 writeIndex。

3. 在末尾填零：一旦所有有效的操作都完成，從當前的 writeIndex 開始到陣列的結尾，用零填充剩餘的部分，以確保所有非零元素都被緊湊地安置在開頭，隨之而來的是零。

4. 返回修改後的陣列：最後，返回已修改的陣列，該陣列現在正確地應用了所有操作，且所有的零都已移動到末尾。

這個演算法的時間複雜度是 $O(n)$，這是有效的，因為它涉及進行所有必要操作的單次通過，然後再進行一次來填充零。空間複雜度是 $O(1)$，因為我們在不需要額外空間的情況下對陣列進行原地修改。

程式碼

C++

class Solution {
public:
    vector<int> applyOperations(vector<int>& nums) {
        int writeIndex = 0;
        int readIndex = 0;

        // 遍歷輸入的陣列
        for (; readIndex < nums.size(); readIndex++) {
            // 如果當前元素為零則跳過
            if (nums[readIndex] == 0) 
                continue;
            
            // 如果當前元素等於下一個元素，將其乘以2並將下一個元素標記為零
            else if (readIndex < nums.size() - 1 && nums[readIndex] == nums[readIndex + 1]) {
                nums[writeIndex++] = nums[readIndex++] * 2;
            }
            // 否則，只需將當前元素移動至寫入位置
            else {
                nums[writeIndex++] = nums[readIndex];
            }
        }

        // 將陣列剩餘部分填充為零
        for (; writeIndex < nums.size(); writeIndex++) 
            nums[writeIndex] = 0;

        return nums;
    }
};

Python

class Solution:
    def applyOperations(self, nums):
        writeIndex = 0
        readIndex = 0

        # 遍歷輸入陣列
        while readIndex < len(nums):
            # 如果當前元素是零則跳過
            if nums[readIndex] == 0:
                readIndex += 1
                continue

            # 如果當前元素和下一個元素相等，將它乘以2並將下一個標記為零
            elif readIndex < len(nums) - 1 and nums[readIndex] == nums[readIndex + 1]:
                nums[writeIndex] = nums[readIndex] * 2
                writeIndex += 1
                readIndex += 1

            # 否則，只需將當前元素移動到寫入位置
            else:
                nums[writeIndex] = nums[readIndex]
                writeIndex += 1

            readIndex += 1

        # 用零填充剩餘的陣列
        while writeIndex < len(nums):
            nums[writeIndex] = 0
            writeIndex += 1

        return nums

複雜度分析

• 時間複雜度: $O(n)$
  該演算法包含兩個主要的迴圈。第一個迴圈對陣列的元素進行操作並重新排列非零元素，第二個迴圈在陣列的末端填充零。每個迴圈最多運行 $n$ 次，其中 $n$ 是陣列 nums 的大小。因此，整體時間複雜度為 $O(n)$。

• 空間複雜度: $O(1)$
  該演算法直接在輸入陣列 nums 上操作，未使用任何隨輸入大小擴展的額外資料結構，除了一些用於索引的整數變數。因此，空間複雜度為 $O(1)$。