题目描述
给你一个非负整数数组 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
题目难度——简单
方法一:直接模拟
按照题目说的,我们在每一步找到当前数组中最小的非零整数,然后执行操作,直到所有元素和为0。
代码/Python
class Solution:
def minimumOperations(self, nums: list[int]) -> int:
total = sum(nums)
res = 0
size = len(nums)
while total:
minium = 101
for x in nums:
if x < minium and x:
minium = x
for i in range(size):
if nums[i] > 0:
nums[i] -= minium
total -= minium
res += 1
return res
方法二:哈希表
直接模拟可以看到是比较慢的,进一步思考,我们在每一步都把当前元素里最小的元素都减掉,就能保证最少的操作次数,而我们不必关心具体的数值是多少,只在乎有多少个不同的数就行了,每次减去当前最小的非0整数就可以。
代码/Python
class Solution:
def minimumOperations(self, nums: list[int]) -> int:
count = Counter(nums)
return sum(k != 0 for k, v in count.items())
总结
方法一时间复杂度O(N),空间复杂度O(1), 方法二时间复杂度O(N),空间复杂度O(N)。