跳至主要內容

2357. 使数组中所有元素都等于零

2357. 使数组中所有元素都等于零

🟢   🔖  贪心 数组 哈希表 排序 模拟 堆（优先队列）  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given a non-negative integer array nums. In one operation, you must:

  • Choose a positive integer x such that x is less than or equal to the smallest non-zero element in nums.
  • Subtract x from every positive element in nums.

Return _theminimum number of operations to make every element in _numsequal to0.

Example 1:

Input: nums = [1,5,0,3,5]

Output: 3

Explanation:

In the first operation, choose x = 1. Now, nums = [0,4,0,2,4].

In the second operation, choose x = 2. Now, nums = [0,2,0,0,2].

In the third operation, choose x = 2. Now, nums = [0,0,0,0,0].

Example 2:

Input: nums = [0]

Output: 0

Explanation: Each element in nums is already 0 so no operations are needed.

Constraints:

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

题目大意

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

解题思路

每次减去的数可以看作是当前数组中非零元素的一个 "独特值"。因此，最终结果取决于数组中有多少个独特的非零值。使用一个集合（Set）来记录数组中所有的非零值，集合的大小即为结果。

  1. 初始化一个集合，用来存储数组中的非零值。
  2. 遍历数组，将所有非零值加入集合中。
  3. 返回集合的大小。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组的长度，遍历数组。
  • 空间复杂度：O(k)，其中 k 是数组中不同的非零值的数量，使用了集合来记录非零元素。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumOperations = function (nums) {
	return new Set(nums.filter((num) => num > 0)).size;
};

相关题目

题号标题题解标签难度力扣
217存在重复元素[✓]数组 哈希表 排序🟢🀄️open in new window 🔗open in new window