LeetCode Ts-2870. Minimum Number of Operations to Make Array Empty

    AllenLi
    CodingLeetCode Js-Hash Table

    You are given a 0-indexed array nums consisting of positive integers.
    There are two types of operations that you can apply on the array any number of times:
    Choose two elements with equal values and delete them from the array.
    Choose three elements with equal values and delete them from the array.
    Return the minimum number of operations required to make the array empty, or -1 if it is not possible.

    你給予一個從 0 位置開始的陣列 nums，陣列中包含正整數。
你可以對陣列執行以下兩種操作，且不限次數：
選擇兩個相等的元素，並從陣列中刪除他們。
選擇三個相等的元素，並從陣列中刪除他們。
回傳讓陣列為空所需的最少操作次數，如果無法清除陣列，則回傳 -1。

    Example 1:

    Input: nums = [2,3,3,2,2,4,2,3,4]
Output: 4
Explanation: We can apply the following operations to make the array empty:
- Apply the first operation on the elements at indices 0 and 3. The resulting array is nums = [3,3,2,4,2,3,4].
- Apply the first operation on the elements at indices 2 and 4. The resulting array is nums = [3,3,4,3,4].
- Apply the second operation on the elements at indices 0, 1, and 3. The resulting array is nums = [4,4].
- Apply the first operation on the elements at indices 0 and 1. The resulting array is nums = [].
It can be shown that we cannot make the array empty in less than 4 operations.

    Example 2:

    Input: nums = [2,1,2,2,3,3]
Output: -1
Explanation: It is impossible to empty the array.

    Solution:
    用 count 統計每個數出現次數，
    然後對每個數：

    出現 1 次 → 回傳 -1（不能刪）
出現 2 或 3 次 → +1 次操作
出現更多 → 盡量用 3 個一組刪，
若剩 1 或 2 個，再補用 2 個一組刪。
最後回傳總操作次數。

// 可被 3 整除，除以 3 可以得到次數。 
// ex. number = 6 (3 + 3)
number % 3 = 0 

// 被 3 除後剩下 1，把其中一組 3 改成 2 + 2，也就是先手動 - 4 在除 3，這個 4 可以得到 2 的次數(2 + 2)。 
// ex. number = 7 (2 + 2 + 3)
number % 3 = 1 

// 被 3 除後剩下 2，先扣 2 在除以 3。
// ex. number = 5 (2 + 3)
number $ 3 = 2

    Code 1: BigO(n)

    function minOperations(nums: number[]): number {
    const count: Map = new Map();
    for (const n of nums) {
        count.set(n, (count.get(n) || 0) + 1);
    }

    let ops: number = 0;
    for (const c of count.values()) {
        if (c === 1) return -1;
        if (c === 2 || c === 3) {
            ops += 1;
            continue;
        }

        const remainder: number = c % 3;
        if (remainder === 0) {
            ops += c / 3;
        } else if (remainder === 1) {
            ops += Math.floor((c - 4) / 3) + 2;
        } else {
            ops += Math.floor((c - 2) / 3) + 1;
        }
    }
    return ops;
};

    FlowChart:
    Example 1

    Input: nums = [2,3,3,2,2,4,2,3,4]

count Map(3) { 2 => 4, 3 => 3, 4 => 2 }
c 4, remainder 1, ops 2
c 3, ops 3
c 2, ops 4
return ops; // 4

    Example 2

    Input: nums = [2,1,2,2,3,3]

count Map(3) { 2 => 3, 1 => 1, 3 => 2 }
c 3, ops = 1
c 1 return -1

    Related Posts