LeetCode 题解工作台
使数组中所有元素都等于零
给你一个非负整数数组 nums 。在一步操作中，你必须： 选出一个正整数 x ， x 需要小于或等于 nums 中 最小 的 非零 元素。 nums 中的每个正整数都减去 x 。 返回使 nums 中所有元素都等于 0 需要的 最少 操作数。 示例 1： 输入： nums = [1,5,0,3,5]…
6
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们观察到，每一次操作，都可以把数组 中相同且非零的元素减少到 ，因此，我们只需要统计数组 中有多少个不同的非零元素，即为最少操作数。统计不同的非零元素，可以使用哈希表或数组来实现。 时间复杂度 ，空间复杂度 。其中 为数组 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个非负整数数组 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 <= 1000 <= nums[i] <= 100
解题思路
方法一：哈希表或数组
我们观察到，每一次操作，都可以把数组 中相同且非零的元素减少到 ，因此，我们只需要统计数组 中有多少个不同的非零元素，即为最少操作数。统计不同的非零元素，可以使用哈希表或数组来实现。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
return len({x for x in nums if x})
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for efficient handling of unique elements in the array.
- question_mark
Test the ability to minimize operations by choosing the smallest non-zero value.
- question_mark
Evaluate how well the candidate can implement array manipulation using sorting or hash tables.
常见陷阱
外企场景- error
Failing to track all unique non-zero values efficiently.
- error
Not properly updating the array after each operation.
- error
Misunderstanding the pattern of subtracting the smallest values first.
进阶变体
外企场景- arrow_right_alt
Handling arrays with many repeated elements efficiently.
- arrow_right_alt
Working with larger arrays or more complex constraints.
- arrow_right_alt
Exploring more optimized algorithms or approaches for minimal operation counting.