題目資訊

• 題目編號: 3396
• 題目連結: Minimum Number of Operations to Make Elements in Array Distinct
• 主題: Array, Hash Table

題目敘述

您有一個整數數組 nums。您需要確保數組中的元素是不同的。為了達到這個目標，您可以執行以下操作任意次數：

• 從數組的開頭移除 3 個元素。如果數組少於 3 個元素，則移除所有剩餘元素。

注意空數組被認為具有不同的元素。返回使數組中的元素不同所需的最少操作次數。

範例 1：

• 輸入: nums = [1,2,3,4,2,3,3,5,7]

• 輸出: 2

• 解釋：

  • 在第一次操作中，移除了前 3 個元素，得到數組 [4, 2, 3, 3, 5, 7]。
  • 在第二次操作中，移除了接下來的 3 個元素，得到數組 [3, 5, 7]，其中的元素是不同的。

  因此，答案是 2。

範例 2：

• 輸入: nums = [4,5,6,4,4]

• 輸出: 2

• 解釋：

  • 在第一次操作中，移除了前 3 個元素，得到數組 [4, 4]。
  • 在第二次操作中，移除所有剩餘元素，得到空數組。

  因此，答案是 2。

範例 3：

• 輸入: nums = [6,7,8,9]

• 輸出: 0

• 解釋：

  數組已經包含不同的元素。因此，答案是 0。

約束條件：

• $1 \leq nums.length \leq 100$
• $1 \leq nums[i] \leq 100$

直覺

此問題需要透過從陣列開頭移除三個元素，以使陣列中所有元素皆獨特。挑戰在於確定所需的最少操作次數。直觀來看，當我們遇到重複元素時，可能已經執行的移除操作足以確保隨後的重複元素不會影響陣列剩餘元素的獨特性。因此，如果我們從陣列末端迭代至開頭時發現重複元素，那麼在此點之前進行的操作次數即為所需的結果。

解法

此解法涉及使用一個布林向量來追蹤在遍歷輸入陣列 nums 時已經出現過的數字。我們將詳細闡述演算法的步驟：

1. 初始化: 創建一個大小為 105 且初始值為 false 的布林向量 isPresent。該向量用來標記哪些數字已經被遇到，這是基於題目限制條件，即 nums 中的數字範圍在 1 到 100 之間。

2. 逆向遍歷: 從陣列 nums 的最後一個元素開始遍歷直到第一個元素。這樣的逆向遍歷可以快速確定任何重複元素的最後位置。

3. 檢查存在性: 對於每個元素，檢查其是否在 isPresent 向量中已被標記為存在。如果是，則表示找到了一個重複元素。

4. 計算操作: 在找到重複元素時，使用公式 $i / 3 + 1$ 計算使陣列元素獨特所需的最小操作次數，其中 $i$ 是目前元素從末端計算的索引位置。除以 3 是為了計算達到該索引位置所需的三個元素移除操作數，而加 $1$ 表示正在進行的操作。

5. 標記元素: 如果這個數字不是重複的，則在 isPresent 中標記它為已看到，然後繼續遍歷下一個元素。

6. 返回零: 如果遍歷所有元素後沒有發現重複元素，則說明從一開始陣列就是獨特的，不需要任何操作。因此，返回 0。

藉由採用此逆向遍歷策略，演算法有效計算出最少操作次數，而無需多次修改陣列，確保了解的最佳解決方案。

程式碼

C++

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        // 建立一個布林向量來追蹤在陣列中數字的存在性。
        // 大小設為105，以覆蓋可能的數字範圍[1, 100]。
        vector<bool> isPresent(105, false);

        // 從陣列的末端向前遍歷。
        for (int i = nums.size() - 1; i >= 0; i--) {
            // 如果數字已經出現過，計算並返回所需操作次數。
            if (isPresent[nums[i]]) {
                return i / 3 + 1;
            }
            // 將該數字標記為已出現。
            isPresent[nums[i]] = true;
        }

        // 如果所有元素都是不重複的，則不需要進行操作。
        return 0;
    }
};

Python

class Solution:
    def minimumOperations(self, nums):
        # 建立一個布林列表來追蹤數字在陣列中的存在性。
        # 大小設為105以涵蓋可能的數字範圍[1, 100]。
        isPresent = [False] * 105

        # 從後往前遍歷陣列。
        for i in range(len(nums) - 1, -1, -1):
            # 如果數字已經出現過，計算並返回所需的操作次數。
            if isPresent[nums[i]]:
                return i // 3 + 1
            # 將數字標記為已出現。
            isPresent[nums[i]] = True

        # 如果所有元素都是獨特的，則不需要任何操作。
        return 0

複雜度分析

• 時間複雜度: $O(n)$，其中 $n$ 為陣列 nums 的長度。這是因為演算法從陣列 nums 的最後一個元素迭代至第一個元素，依次檢查並標記 isPresent 向量中的每個元素。在每次迭代中的處理（檢查和標記元素）均需恆定時間，故整體的時間複雜度為 $O(n)$。

• 空間複雜度: $O(1)$。這是因為演算法使用的額外空間與輸入大小 $n$ 無關。向量 isPresent 是一個固定大小為 105 的向量，與 nums 的大小無關。因此，空間複雜度為常數，即 $O(1)$。