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

题目

https://leetcode.cn/problems/minimum-number-of-operations-to-make-elements-in-array-distinct/description/?envType=daily-question&envId=2025-04-08

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

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

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

实现

思路：倒序遍历，找到离下标 0 最远位置的重复元素的下标 k,k/3

• 例如 $nums=[1,2,3,4,2,3,3,5,7]$，最远重复元素是 3，下标是 6
• 那么把下标 6 之前的元素全部移除需要 2 次

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

/**
 * @param {string} s
 * @return {string}
 */
var minimumOperations = function (nums) {
    const n = nums.length;
    const s = new Set();
    let k = -1;
    for (let i = n - 1; i >= 0; i--) {
        if (s.has(nums[i])) {
            k = i + 1;
            break;
        }
        s.add(nums[i]);
    }
    return Math.ceil(k / 3);
};