Easy

题目描述

给你一个非负整数数组 nums。在一次操作中，你必须：

  • 选择一个正整数 x，使得 x 小于或等于 nums 中最小的非零元素。
  • 从 nums 中的每个正元素中减去 x。

返回使 nums 中每个元素都等于 0 所需的最小操作数。

示例 1：

输入：nums = [1,5,0,3,5]
输出：3
解释：
第一次操作，选择 x = 1。现在，nums = [0,4,0,2,4]。
第二次操作，选择 x = 2。现在，nums = [0,2,0,0,2]。
第三次操作，选择 x = 2。现在，nums = [0,0,0,0,0]。

示例 2：

输入：nums = [0]
输出：0
解释：nums 中的每个元素都已经是 0，所以不需要操作。

约束条件：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

解题思路

这道题的核心洞察是：操作数等于数组中不同非零元素的个数。

让我们分析一下为什么：

  1. 最优策略：每次操作都应该选择当前最小的非零元素作为 x。这样可以保证至少有一个元素变为 0，同时其他元素也尽可能减小。

  2. 关键观察：具有相同值的元素总是需要相同次数的操作才能变为 0，而具有不同值的元素总是需要不同次数的操作。

  3. 推理过程：

    • 第一次操作：选择最小非零值，所有等于这个值的元素都变为 0
    • 第二次操作：选择剩余元素中的最小非零值，所有等于这个新最小值的元素都变为 0
    • 重复此过程，直到所有元素都为 0

因此，我们只需要统计数组中有多少个不同的非零数字即可。

解法对比：

  • 哈希集合法（推荐）：直接统计不同非零元素的个数，时间复杂度O(n)
  • 排序法：先排序再统计，时间复杂度O(n log n)
  • 模拟法：实际执行操作过程，时间复杂度较高

哈希集合法是最优解，代码简洁且效率最高。

代码实现

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        unordered_set<int> uniqueNonZero;
        for (int num : nums) {
            if (num > 0) {
                uniqueNonZero.insert(num);
            }
        }
        return uniqueNonZero.size();
    }
};

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        return len(set(num for num in nums if num > 0))

public class Solution {
    public int MinimumOperations(int[] nums) {
        HashSet<int> uniqueNonZero = new HashSet<int>();
        foreach (int num in nums) {
            if (num > 0) {
                uniqueNonZero.Add(num);
            }
        }
        return uniqueNonZero.Count;
    }
}

var minimumOperations = function(nums) {
    const uniqueNonZero = new Set();
    for (const num of nums) {
        if (num > 0) {
            uniqueNonZero.add(num);
        }
    }
    return uniqueNonZero.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
哈希集合法O(n)O(k)

其中 n 是数组长度，k 是不同非零元素的个数（k ≤ min(n, 100)）

相关题目