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 List

class 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 + 1
            se.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 main

func 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和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源