題目資訊

• 題目編號: 3375
• 題目連結: Minimum Operations to Make Array Values Equal to K
• 主題: Array, Hash Table

題目敘述

你有一個整數陣列 nums 和一個整數 k。

如果陣列中所有嚴格大於 $h$ 的值都相同，則整數 $h$ 稱為有效。

例如，若 $nums = [10, 8, 10, 8]$，則 $h = 9$ 是一個有效整數，因為所有 $nums[i] > 9$ 都等於 10，但 5 不是一個有效整數。

你可以對 nums 執行以下操作：

• 選擇一個對於當前nums 數值有有效的整數 $h$。
• 對於每一個索引 $i$，如果 $nums[i] > h$，則將 $nums[i]$ 設為 $h$。

返回使陣列中每一個元素等於k 所需的最少操作次數。如果不可能讓所有元素等於 k，則返回 -1。

範例 1:

輸入: nums = [5,2,5,4,5], k = 2

輸出: 2

解釋:

可以按順序使用有效整數 4 和 2 來執行操作。

範例 2:

輸入: nums = [2,1,2], k = 2

輸出: -1

解釋:

不可能使所有數值等於 2。

範例 3:

輸入: nums = [9,7,5,3], k = 1

輸出: 4

解釋:

可以按 7, 5, 3 和 1 的順序使用有效整數來進行操作。

限制條件:

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

直覺

此問題的目標是將數組 nums 轉換為所有元素都等於給定整數 k 的數組。這種轉換是通過允許我們反覆選擇一個有效整數 h，將 nums 中大於 h 的元素縮減為 h 的值來完成的。核心挑戰在於盡可能地減少所需的操作次數，或者如果原始數組中任何元素小於 k，則確定這種轉換是不可能的。

為了解決這個問題，關鍵觀察是：任何小於 k 的 nums 中的值立即表明轉換是不可能的。此外，如果所有元素至少為 k，我們可以按降序依次減少大於 k 的所有數值，直到所有元素都等於 k。

解法

此解法使用了 set 並結合一些簡單檢查來以最小的操作次數確保正確性：

1. 檢查不可能情況：
   首先，我們判斷將所有數組元素轉換為 k 是否立即不可能。當 nums 中的最小元素小於 k 時，這種情況就會發生。利用 min_element 函數可以有效地找到最小值，從而在必要時快速返回 -1。

2. 利用集合存儲唯一值：
   使用 set，我們收集 nums 的所有唯一元素。每個唯一數字代表一個不同的潛在有效整數 h，可以幫助將元素縮減為 k。如果 nums 滿足所有元素大於或等於 k 這一初始條件，我們知道該方法可以進一步推進。

3. 計算操作數量：
   任務簡化為確定有多少唯一值大於 k。這些唯一值的數量決定了需要多少操作才能將數組縮減為全 k，因為每次操作可以一致地降低未被縮減到 k 的最大一組元素。

4. 針對初始等於 k 的調整：
   最後，考慮最小元素是否已經是 k。如果是這種情況，則只需要少一個轉換，因為基準值 k 已經達成，無需進一步的縮減操作。

通過這些步驟，該演算法有效地計算出所需的最少操作數，或者確認轉換數組是不可實現的。這種策略性地結合集合邏輯和條件檢查，在定義的限制條件範疇內提供了解決方案。

程式碼

C++

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        // 檢查在 'nums' 中是否有任一元素小於 'k'。
        // 如果有，則無法使所有元素等於 'k'，返回 -1。
        if (*min_element(nums.begin(), nums.end()) < k) {
            return -1;
        }

        // 建立一個集合來儲存 'nums' 中的唯一元素。
        set<int> uniqueElements;
        for (int num : nums) {
            uniqueElements.insert(num);
        }

        // 計算大於 'k' 的唯一元素數量。
        // 我們需要一個操作來使元素等於 'k'，如果 'k' 尚未是最小值。
        return uniqueElements.size() - 1 + 
               (*min_element(nums.begin(), nums.end()) == k ? 0 : 1);
    }
};

Python

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        # 檢查是否存在'nums'中的任何元素小於'k'。
        # 如果是這樣，就不可能使所有元素等於'k'，返回-1。
        if min(nums) < k:
            return -1

        # 創建一個集合來存儲'nums'中的獨特元素。
        uniqueElements = set()
        for num in nums:
            uniqueElements.add(num)

        # 計算大於'k'的獨特元素數量。
        # 如果'k'不是已經的最小值，我們需要一個操作來使元素等於'k'。
        return len(uniqueElements) - 1 + (0 if min(nums) == k else 1)

複雜度分析

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

  時間複雜度主要由集合上的操作和 min_element 函數驅動。將每個元素插入到集合中單個元素需要 $O(\log n)$ 的時間，且這一操作對 nums 陣列中的每一個 $n$ 個元素都需執行，因此總共需要 $O(n \log n)$ 的時間。min_element 函數被使用了兩次，其時間複雜度為 $O(n)$。因此，總的時間複雜度為 $O(n \log n) + O(n)$，簡化後為 $O(n \log n)$。

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

  空間複雜度由集合 uniqueElements 所需的空間決定，該集合最多可以容納來自 nums 陣列的 $n$ 個獨特元素。因此，空間複雜度為 $O(n)$。需要注意的是，像 min_element 這樣的操作會使用額外的空間來存放迭代器和返回值，但這些並不足以影響整體的空間複雜度。