2357. 使数组中所有元素都等于零
题目描述
给你一个非负整数数组 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
算法一：模拟
思路
- 一开始先使用 accumulate 函数对数组各元素进行相加，判断数组中各元素是否为 0 ，如果 accumulate 返回 0 ，那么就得到答案 。
- 首先将各元素按照从小到大的顺序排序，这样比较容易获得 “最小非零元素” ；
- 遍历排序后的数组 nums ，找到第一个非0元素，也就得到了题目所要求的“最小非零元素”，记为 m；
- 遍历数组 nums ，将 大于等于 m 的元素都减掉 0，这样就完成了一次操作。
收获
- 复习了 accumulate 函数的使用；
- 一开始忘记了相减的前提：该元素大于等于 m ，导致出错。
sort(nums.begin(), nums.end());默认从小到大排序，每次都会忘记！
算法情况
- 时间复杂度：O（n logn），即使用 sort 函数所花费的时间。
- 空间复杂度：O（1）
代码
class Solution {
public:int minimumOperations(vector<int>& nums) {int ans = 0, m = 0;while(1){// 如果nums数组各元素和为0 则问题结束if(!accumulate(nums.begin(), nums.end(), 0)) return ans;// 排序 使元素从小到大排序sort(nums.begin(), nums.end()); for(int & t : nums){if(t > 0){m = t;break;}}for(int & t : nums){// 减法if(t >= m) t -= m;}ans ++;}}
};
算法二：哈希表
思路
- 观察到每次操作都能使得数组中相同且非 0 元素减少到 0 ，因此，只需要统计数组中有多少个不同的非 0 元素即可 ，这就是最小操作数， 可以用哈希表实现。
收获
- 这个方法更简单，主要是在思路的转换。
算法情况
- 时间复杂度：O（n），其中 n 为 nums 的长度。
- 空间复杂度：O（C），其中 C 为 105。
代码
class Solution {
public:int minimumOperations(vector<int>& nums) {int ans = 0;vector<bool> s(105);s[0] = true; // 保证统计的元素都非0for(int &x : nums){if(!s[x]){ans ++;s[x] = true; // 不会再统计该元素}}return ans;}
};
