Medium

题目描述

给你一个整数数组 nums。

在一次操作中，你可以移除当前数组的前三个元素。如果剩余元素少于三个，则移除所有剩余元素。

重复此操作，直到数组为空或不包含重复值。

返回所需的操作次数。

示例 1：

输入：nums = [3,8,3,6,5,8]
输出：1
解释：
在第一次操作中，我们移除前三个元素。剩余元素 [6, 5, 8] 都是不同的，所以我们停止。只需要一次操作。

示例 2：

输入：nums = [2,2]
输出：1
解释：
一次操作后，数组变为空，满足停止条件。

示例 3：

输入：nums = [4,3,5,1,2]
输出：0
解释：
数组中的所有元素都是不同的，因此不需要任何操作。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

解题思路

解题思路

这道题的核心是模拟题目描述的操作过程。我们需要：

  1. 检查当前数组是否有重复元素：使用哈希表记录每个元素的出现次数
  2. 模拟移除操作：如果存在重复元素，移除前三个元素（或剩余所有元素）
  3. 重复直到满足条件：继续操作直到数组为空或所有元素都不重复

算法步骤：

  • 使用指针 start 标记当前有效数组的起始位置
  • 用哈希表统计当前有效范围内每个元素的出现次数
  • 检查是否存在重复元素（出现次数 > 1）
  • 如果有重复，执行一次操作：移除前三个元素，更新哈希表和指针
  • 重复直到无重复元素或数组为空

时间复杂度优化： 每次操作后只需要更新被移除元素在哈希表中的计数，避免重新遍历整个数组。

这种方法直接模拟了题目要求的过程，逻辑清晰且实现简单。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int start = 0;
        int operations = 0;
        
        while (start < n) {
            // 统计当前范围内每个元素的出现次数
            unordered_map<int, int> count;
            for (int i = start; i < n; i++) {
                count[nums[i]]++;
            }
            
            // 检查是否有重复元素
            bool hasDuplicate = false;
            for (auto& p : count) {
                if (p.second > 1) {
                    hasDuplicate = true;
                    break;
                }
            }
            
            if (!hasDuplicate) {
                break;
            }
            
            // 执行一次操作：移除前三个元素
            start += 3;
            operations++;
        }
        
        return operations;
    }
};

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        start = 0
        operations = 0
        n = len(nums)
        
        while start < n:
            # 统计当前范围内每个元素的出现次数
            count = {}
            for i in range(start, n):
                count[nums[i]] = count.get(nums[i], 0) + 1
            
            # 检查是否有重复元素
            has_duplicate = any(c > 1 for c in count.values())
            
            if not has_duplicate:
                break
            
            # 执行一次操作：移除前三个元素
            start += 3
            operations += 1
        
        return operations

public class Solution {
    public int MinOperations(int[] nums) {
        int start = 0;
        int operations = 0;
        int n = nums.Length;
        
        while (start < n) {
            // 统计当前范围内每个元素的出现次数
            Dictionary<int, int> count = new Dictionary<int, int>();
            for (int i = start; i < n; i++) {
                if (count.ContainsKey(nums[i])) {
                    count[nums[i]]++;
                } else {
                    count[nums[i]] = 1;
                }
            }
            
            // 检查是否有重复元素
            bool hasDuplicate = false;
            foreach (var kvp in count) {
                if (kvp.Value > 1) {
                    hasDuplicate = true;
                    break;
                }
            }
            
            if (!hasDuplicate) {
                break;
            }
            
            // 执行一次操作：移除前三个元素
            start += 3;
            operations++;
        }
        
        return operations;
    }
}

var minOperations = function(nums) {
    let start = 0;
    let operations = 0;
    const n = nums.length;
    
    while (start < n) {
        // 统计当前范围内每个元素的出现次数
        const count = new Map();
        for (let i = start; i < n; i++) {
            count.set(nums[i], (count.get(nums[i]) || 0) + 1);
        }
        
        // 检查是否有重复元素
        let hasDuplicate = false;
        for (const [num, cnt] of count) {
            if (cnt > 1) {
                hasDuplicate = true;
                break;
            }
        }
        
        if (!hasDuplicate) {
            break;
        }
        
        // 执行一次操作：移除前三个元素
        start += 3;
        operations++;
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)最坏情况下需要 O(n/3) 次操作，每次操作需要 O(n) 时间统计元素频次
空间复杂度O(n)哈希表存储元素频次，最多存储 n 个不同元素