[LeetCode] 每日一题 3396. 使数组元素互不相同所需的最少操作次数（简单数学计算）

题目描述

给你一个整数数组 nums，你需要确保数组中的元素 互不相同 。为此，你可以执行以下操作任意次：

• 从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。

注意：空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数 。

题目链接

https://leetcode.cn/problems/minimum-number-of-operations-to-make-elements-in-array-distinct

示例输入

示例 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

解题思路

今天这题属于一道 思维题 + 数学模拟题，整体难度不高，关键在于如何理解题目中的“移除三个元素”这一操作，以及如何巧妙地处理判重。

起初我也考虑过直接模拟操作过程，但发现判断起来太麻烦，还涉及频繁地判断元素是否重复、维护状态、不断更新数组，很容易出错。

但我们注意到一个关键点：操作总是从开头移除元素，那么就可以转换思路，从 后往前找出最长的不重复子数组，也就是只要知道从后往前最多能保留多少个互不相同的数，就可以快速计算出我们至少要移除多少组元素。

举个例子，如果第 i 个元素是第一次出现的重复元素，那它和前面的部分就都不能保留，我们需要移除 i / 3 + 1 次，才能确保剩下部分不包含重复值。

class Solution {
    public int minimumOperations(int[] nums) {
        boolean[] contains = new boolean[101];
        for (int i = nums.length - 1; i >= 0; i--) {
            if (contains[nums[i]]) {
                return i / 3 + 1;
            }
            contains[nums[i]] = true;
        }
        return 0;
    }
}

复杂度分析

• 时间复杂度：O(n)，我们只需要从后往前遍历一遍数组即可 🚀

• 空间复杂度：O(1)，使用了一个固定大小的布尔数组 contains 来判断元素是否重复 ✅

总结

这题虽然在操作描述上有点“绕”，但其实是一道典型的找规律 + 倒推 + 数学计算的题。看似要模拟，其实换个角度思考，就可以把问题转化成更容易处理的形式。做题过程中再次体会到，操作有方向性（从头移除）时，反向遍历往往更高效。

有空也可以用集合、HashSet 做一版暴力模拟，再对比一下思路和性能差异，会有更多收获 🔍

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。