题目描述

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

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

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

样例

输入： nums = [1,2,3,4,2,3,3,5,7]

输出： 2

解释：

第一次操作：移除前 3 个元素，数组变为 [4, 2, 3, 3, 5, 7]。
第二次操作：再次移除前 3 个元素，数组变为 [3, 5, 7]，此时数组中的元素互不相同。
因此，答案是 2。

输入： nums = [4,5,6,4,4]

输出： 2

解释：

第一次操作：移除前 3 个元素，数组变为 [4, 4]。
第二次操作：移除所有剩余元素，数组变为空。
因此，答案是 2。

输入： nums = [6,7,8,9]

输出： 0

解释：

数组中的元素已经互不相同，因此不需要进行任何操作，答案是 0。

限制

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

算法

(倒序遍历，哈希表) $O(n)$

1. 倒序遍历数组，用哈希表找到第一次出现重复元素的位置 $i$。
2. 则需要保证 $i$ 以及 $i$ 之前的元素都需要被移除。
3. 根据题意计算出操作次数。

时间复杂度

• 最多遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        const int n = nums.size();
        unordered_set<int> h;

        int i;
        for (i = n - 1; i >= 0; i--) {
            if (h.find(nums[i]) != h.end())
                break;

            h.insert(nums[i]);
        }

        return i < 0 ? 0 : i / 3 + 1;
    }
};