3396. 使数组元素互不相同所需的最少操作次数(简单)

1，问题描述

给你一个整数数组 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 <= nums.length <= 100
• 1 <= nums[i] <= 100

2，初步思考

​ 直接找到最大的一个需要被删除的id即可

3，代码处理

package days;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class _3396使数组元素互不相同所需的最少操作次数 {

    // 反向查找，速度更快
    public int minimumOperations_reverse(int[] nums) {
        boolean[] dp = new boolean[101];
        int n = nums.length;
        for (int i = n - 1; i >= 0; i--) {
            if (dp[nums[i]]) {
                return (i + 1) / 3 + ((i + 1) % 3 > 0 ? 1 : 0);
            }
            dp[nums[i]] = true;
        }
        return 0;
    }

    // 缓存索引idx，正向查找
    public int minimumOperations(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        int idxRight = 0, idxTemp = -1;
        while (idxRight < n) {
            if (map.containsKey(nums[idxRight])) {
                idxTemp = Math.max(map.get(nums[idxRight]), idxTemp);
            }
            map.put(nums[idxRight], idxRight);
            idxRight++;
        }
        return (idxTemp + 1) / 3 + ((idxTemp + 1) % 3 > 0 ? 1 : 0);
    }

    public int minimumOperations_dp(int[] nums) {
        int[] dp = new int[101];
        Arrays.fill(dp, -1);
        int n = nums.length;
        int idxRight = 0, idxTemp = -1;
        while (idxRight < n) {
            if (dp[nums[idxRight]] >= 0) {
                idxTemp = Math.max(dp[nums[idxRight]], idxTemp);
            }
            dp[nums[idxRight]] = idxRight;
            idxRight++;
        }
        return (idxTemp + 1) / 3 + ((idxTemp + 1) % 3 > 0 ? 1 : 0);
    }

    public static void main(String[] args) {
        _3396使数组元素互不相同所需的最少操作次数 test = new _3396使数组元素互不相同所需的最少操作次数();
        int[] nums = {7, 8, 85, 64, 16, 9, 17, 10, 5, 80, 21};
//        int[] nums = {1, 5, 3, 2, 1, 3, 1};
//        int[] nums = {1,2,3,4,2,3,3,5,7};s
//        int[] nums = {4, 5, 6, 4, 4};
//        int[] nums = {5, 5};
//        int[] nums = {15, 3, 5, 5};
//        int[] nums = {2, 7, 15, 1, 15};
//        int[] nums = {6,7,8,9};
        System.out.println(test.minimumOperations_reverse(nums));
    }
}