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

解法

方法一：哈希表 + 倒序遍历

我们可以倒序遍历数组 $\textit{nums}$，并使用哈希表 $\textit{s}$ 记录已经遍历过的元素。当遍历到元素 $\textit{nums}[i]$ 时，如果 $\textit{nums}[i]$ 已经在哈希表 $\textit{s}$ 中，那么说明我们需要移除 $\textit{nums}[0..i]$ 的所有元素，需要的操作次数为 $\left\lfloor \frac{i}{3} \right\rfloor + 1$。否则，我们将 $\textit{nums}[i]$ 加入哈希表 $\textit{s}$ 中，并继续遍历下一个元素。

遍历结束后，如果没有找到重复的元素，那么数组中的元素已经互不相同，不需要进行任何操作，答案为 $0$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\textit{nums}$ 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        s = set()
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] in s:
                return i // 3 + 1
            s.add(nums[i])
        return 0

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

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        unordered_set<int> s;
        for (int i = nums.size() - 1; ~i; --i) {
            if (s.contains(nums[i])) {
                return i / 3 + 1;
            }
            s.insert(nums[i]);
        }
        return 0;
    }
};

func minimumOperations(nums []int) int {
    s := map[int]bool{}
    for i := len(nums) - 1; i >= 0; i-- {
        if s[nums[i]] {
            return i/3 + 1
        }
        s[nums[i]] = true
    }
    return 0
}

function minimumOperations(nums: number[]): number {
    const s = new Set<number>();
    for (let i = nums.length - 1; ~i; --i) {
        if (s.has(nums[i])) {
            return Math.ceil((i + 1) / 3);
        }
        s.add(nums[i]);
    }
    return 0;
}

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

题目描述

解法

方法一：哈希表 + 倒序遍历

评论