LeetCode 3396.使数组元素互不相同所需的最少操作次数：O(n)一次倒序遍历

【LetMeFly】3396.使数组元素互不相同所需的最少操作次数：O(n)一次倒序遍历

力扣题目链接：https://leetcode.cn/problems/minimum-number-of-operations-to-make-elements-in-array-distinct/

给你一个整数数组 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

解题方法：遍历

只有一种删除重复元素的方式，就是把开头几个元素都删了。

删到多少为止呢？删到剩余元素全不同为止。

倒序遍历数组，使用一个哈希表记录遍历过程中出现的元素。若当前元素已经出现过，则至少从头删到当前元素。

当前下标为$i$到话，需要删多少次呢？需要删$\lceil \frac{i+1}{3}\rceil =\lfloor \frac{i}{3}\rfloor$次。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(len(nums))$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-04-08 21:52:04* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-04-08 21:54:03*/
class Solution {
public:int minimumOperations(vector<int>& nums) {unordered_set<int> se;for (int i = nums.size() - 1; i >= 0; i--) {if (se.count(nums[i])) {return min((int)nums.size(), i / 3 + 1);}se.insert(nums[i]);}return 0;}
};

Python

'''
Author: LetMeFly
Date: 2025-04-08 21:55:27
LastEditors: LetMeFly.xyz
LastEditTime: 2025-04-08 21:57:08
'''
from typing import Listclass Solution:def minimumOperations(self, nums: List[int]) -> int:se = set()for i in range(len(nums) - 1, -1, -1):if nums[i] in se:return i // 3 + 1se.add(nums[i])return 0

Java

/** @Author: LetMeFly* @Date: 2025-04-08 21:57:38* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-04-08 21:59:04*/
import java.util.Set;
import java.util.HashSet;class Solution {public int minimumOperations(int[] nums) {Set<Integer> se = new HashSet<>();for (int i = nums.length - 1; i >= 0; i--) {if (!se.add(nums[i])) {return i / 3 + 1;}}return 0;}
}

Go

/** @Author: LetMeFly* @Date: 2025-04-08 21:59:54* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-04-08 22:01:57*/
package mainfunc minimumOperations(nums []int) int {se := map[int]struct{}{}for i := len(nums) - 1; i >= 0; i-- {if _, ok := se[nums[i]]; ok {return i / 3 + 1}se[nums[i]] = struct{}{}}return 0
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源