使数组中所有元素都等于零【LC2357】
给你一个非负整数数组
nums。在一步操作中，你必须：
- 选出一个正整数
x，x需要小于或等于nums中 最小 的 非零 元素。nums中的每个正整数都减去x。返回使
nums中所有元素都等于0需要的 最少 操作数。
排序+模拟
- 思路：
- 将数组升序排序后，每次减去的数值
x小于等于数组中第一个非零元素m，为了使操作次数最小，那么应使x=m【贪心】
- 遍历数组中的每个元素
nums[i]，记录当前已经减去的数的总和delNum，那么每次操作后，数组中元素的值为nums[i]-delNum，每遇到一个不为0的数字，操作数加1并更新delNum
- 实现
class Solution { public int minimumOperations(int[] nums) { int n = nums.length; int count = 0, delNum = 0; Arrays.sort(nums); for (int i = 0; i < n; i++){ if (nums[i] - delNum == 0) continue; // delNum += (nums[i] - delNum); delNum = nums[i];// 操作次数取决于数组中不同元素的个数 count++; } return count; } }
复杂度
时间复杂度：O ( n l o g n ) ，n为数组长度，排序所需要的时间复杂度
空间复杂度：O ( 1 )
哈希表
- 思路：可以发现操作次数取决于数组中不相等元素的个数，因此可以使用哈希表记录数组中不同元素的个数
- 实现
class Solution { public int minimumOperations(int[] nums) { int n = nums.length; Set<Integer> set = new HashSet<>(); for (int i = 0; i < n; i++){ if (nums[i] == 0) continue; set.add(nums[i]); } return set.size(); } }
复杂度
- 时间复杂度：O(n)，n为数组长度
- 空间复杂度：O(n)
