Easy

题目描述

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

提示：

  • 约束条件较小，可以尝试暴力解法。

解题思路

解题思路

由于数组长度最多100，我们可以使用暴力模拟的方法来解决这个问题。

核心思路：

  1. 每次操作都是从数组开头移除3个元素（如果不足3个则移除所有）
  2. 我们需要检查当前数组是否所有元素都互不相同
  3. 如果不满足条件，继续执行操作，直到满足为止

具体步骤：

  1. 使用哈希表（或集合）来检查数组中是否有重复元素
  2. 如果没有重复元素，直接返回0
  3. 如果有重复元素，模拟移除前3个元素的操作
  4. 重复步骤1-3，直到数组为空或所有元素互不相同
  5. 返回操作次数

时间复杂度优化： 由于每次操作最多移除3个元素，最多需要⌈n/3⌉次操作，每次检查重复需要O(n)时间，总体复杂度是可接受的。

这种方法简单直观，符合题目暴力求解的提示，在给定的约束条件下效率足够。

代码实现

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int operations = 0;
        
        while (!nums.empty()) {
            // 检查当前数组是否所有元素都互不相同
            unordered_set<int> seen;
            bool hasDuplicate = false;
            
            for (int num : nums) {
                if (seen.count(num)) {
                    hasDuplicate = true;
                    break;
                }
                seen.insert(num);
            }
            
            // 如果没有重复元素，返回操作次数
            if (!hasDuplicate) {
                break;
            }
            
            // 移除前3个元素（如果不足3个则移除所有）
            int removeCount = min(3, (int)nums.size());
            nums.erase(nums.begin(), nums.begin() + removeCount);
            operations++;
        }
        
        return operations;
    }
};

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        operations = 0
        
        while nums:
            # 检查当前数组是否所有元素都互不相同
            if len(set(nums)) == len(nums):
                break
            
            # 移除前3个元素（如果不足3个则移除所有）
            remove_count = min(3, len(nums))
            nums = nums[remove_count:]
            operations += 1
        
        return operations

public class Solution {
    public int MinimumOperations(int[] nums) {
        var numsList = new List<int>(nums);
        int operations = 0;
        
        while (numsList.Count > 0) {
            // 检查当前数组是否所有元素都互不相同
            var seen = new HashSet<int>();
            bool hasDuplicate = false;
            
            foreach (int num in numsList) {
                if (seen.Contains(num)) {
                    hasDuplicate = true;
                    break;
                }
                seen.Add(num);
            }
            
            // 如果没有重复元素，返回操作次数
            if (!hasDuplicate) {
                break;
            }
            
            // 移除前3个元素（如果不足3个则移除所有）
            int removeCount = Math.Min(3, numsList.Count);
            numsList.RemoveRange(0, removeCount);
            operations++;
        }
        
        return operations;
    }
}

var minimumOperations = function(nums) {
    let operations = 0;
    
    while (nums.length > 0) {
        // 检查当前数组是否所有元素都互不相同
        const seen = new Set();
        let hasDuplicate = false;
        
        for (const num of nums) {
            if (seen.has(num)) {
                hasDuplicate = true;
                break;
            }
            seen.add(num);
        }
        
        // 如果没有重复元素，返回操作次数
        if (!hasDuplicate) {
            break;
        }
        
        // 移除前3个元素（如果不足3个则移除所有）
        const removeCount = Math.min(3, nums.length);
        nums.splice(0, removeCount);
        operations++;
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
最坏情况O(n²)O(n)
平均情况O(n²)O(n)

说明：

  • 时间复杂度：最多进行⌈n/3⌉次操作，每次操作需要O(n)时间检查重复元素，总体为O(n²)
  • 空间复杂度：使用哈希表存储元素，最多需要O(n)的额外空间

相关题目