目标
给你一个整数数组 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，那么将重复元素个数减 1，直到重复元素个数为 0，返回操作次数。
网友题解使用逆向思维，倒序遍历数组，直到遇到第一个重复的元素，由于操作是从头开始的，因此一定要删除该重复元素。假如下标是 i，那么需要操作 ⌈(i + 1)/3⌉ = i/3 + 1 次。
对于整数 a >= 0, b > 0，有 ⌈a/b⌉ = ⌊(a + b - 1)/b⌋，将 a = qb + r 带入分析即可。或者直接写 ⌊a/b⌋ + a % b > 0 ? 1 : 0。
正向考虑稍微有点复杂，需要找到重复数字前一个下标中的最大下标。
代码
/**
* @date 2025-04-08 8:43
*/
public class MinimumOperations3396 {
public int minimumOperations_v1(int[] nums) {
int[] index = new int[101];
Set<Integer> set = new HashSet<>();
Arrays.fill(index, -1);
int maxIndex = -1;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (set.contains(num)) {
maxIndex = Math.max(maxIndex, index[num]);
}
set.add(num);
index[num] = i;
}
if (maxIndex == -1) {
return 0;
} else {
return maxIndex / 3 + 1;
}
}
public int minimumOperations(int[] nums) {
int[] cnt = new int[101];
Queue<Integer> q = new ArrayDeque<>();
Set<Integer> set = new HashSet<>();
for (int num : nums) {
q.offer(num);
if (++cnt[num] > 1) {
set.add(num);
}
}
if (set.size() == 0) {
return 0;
}
int sameCnt = set.size();
int res = 0;
while (!q.isEmpty()) {
res++;
for (int i = 0; !q.isEmpty() && i < 3; i++) {
if (--cnt[q.poll()] == 1) {
sameCnt--;
}
}
if (sameCnt == 0) {
break;
}
}
return res;
}
}
性能
