使数组为空的最少操作次数

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.

 

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.

 

Constraints:

• 2 <= nums.length <= 105
• 1 <= nums[i] <= 106

/*
 * 思路：
 * 1. 使用stream流处理数组，首先统计每个元素的出现频率。
 * 2. 将频率映射为需要的操作次数，使用map和reduce方法累加总操作次数。
 * 3. 如果频率不满足条件返回-1。
 */

import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

public class Solution {
    public int minOperations(int[] nums) {
        Map<Integer, Long> freqMap = Arrays.stream(nums)
            .boxed()
            .collect(Collectors.groupingBy(n -> n, Collectors.counting()));

        int operations = freqMap.values().stream()
            .mapToInt(freq -> {
                if (freq % 3 == 0) {
                    return (int) (freq / 3);
                } else if (freq % 3 == 2) {
                    return (int) ((freq - 2) / 3 + 1);
                } else if (freq % 3 == 1) {
                    if (freq < 4) return -1;
                    return (int) ((freq - 4) / 3 + 2);
                }
                return -1;
            })
            .reduce(0, (a, b) -> (a == -1 || b == -1) ? -1 : a + b);

        return operations;
    }
}

这个题解首先使用了Counter类来计算数组中每个数字出现的次数。然后检查如果某个数字的出现次数为1，直接返回-1，因为单个数字无法通过题目给定的操作被删除。如果所有数字的出现次数都不为1，接下来计算最小操作次数：对于每个数字出现的次数c，使用公式(c+2)//3来计算至少需要多少次操作可以删除这些数字。这个公式是基于尽可能多地使用三个相同元素的删除操作，因为这种操作对于减少总操作次数最为有效。最后，将所有数字的操作次数相加得到结果。

O(n)

O(n)