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

题目

给你一个整数数组 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

---

思路

具体步骤如下：

1. 检查当前数组是否有重复元素：
   • 如果没有，则不需要操作，返回0。
   • 如果有，则需要进行至少一次操作。
2. 执行操作：
   • 每次操作移除前三个元素。
   • 每次操作后，检查剩下的数组是否有重复。
   • 重复这个过程，直到剩下的数组没有重复或为空。
3. 最少操作次数：
   • 我们需要找到最早的一个点，使得从该点开始的子数组没有重复。
   • 每次操作都移除三个元素，因此操作次数取决于我们需要移除多少个“块”的三个元素才能到达这个点。

算法设计

为了实现这个逻辑，可以采用以下方法：

1. 从后向前遍历：
   • 我们需要找到一个最长的后缀子数组，其中所有元素都是唯一的。
   • 然后计算需要移除多少个“三个元素”的块才能保留这个唯一后缀。
2. 使用哈希集合检测唯一性：
   • 从数组的末尾开始，向前遍历，使用一个集合来记录已经遇到的元素。
   • 一旦遇到重复的元素，就停止，因为我们需要移除前面的部分以确保唯一性。
3. 计算操作次数：
   • 假设我们需要保留从索引 i 开始的子数组，那么需要移除前 i 个元素。
   • 每次操作移除3个元素，所以操作次数为 ceil(i / 3)。

---

完整代码

class Solution {
    public int minimumOperations(int[] nums) {
        int n=nums.length;
        Set<Integer> ans=new HashSet<>();
        int m=n-1;
        for(;m>=0;m--){
            if(ans.contains(nums[m]))   break;
            ans.add(nums[m]);
        }
        if(m==-1)   return 0;
        int res=m+1;
        return (res+2)/3;
    }
}