【LeetCode】使数组中所有元素都等于零 Java 题解

作者：Albert

2022 年 8 月 03 日
本文字数：1336 字
阅读完需：约 4 分钟

题目描述

给你一个非负整数数组 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 ，所以不需要执行任何操作。
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/make-array-zero-by-subtracting-equal-amounts著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是数组题目，题目给出数组 nums, 要求我们求出返回使 nums 中所有元素都等于 0 需要的最少操作数。在消除的过程中，每次需要消除 x, x 需要小于或等于 nums 中最小的非零元素。
根据题目要求，我们为了达到最小消除次数，我们每次消减数字为当前 nums 的最小值。首先，我们采用朴素解法，对整个数组进行排序，然后遍历排序后的数组，找到的第一个不为 0 的数值，即为此次可消除的数值，然后动态更新数组，完成题意即可，这里使用了排序算法，时间复杂度是 O(n log n)。
朴素解法通过之后，时间复杂度比较高。再次分析题意和代码，需要满足数组元素全部为 0，我们只需要处理不为 0 的部分，而且每次操作，我们可以使某一个不为 0 的元素转化为 0。
通过上述的分析，这个问题就转化成了求数组中不为 0，不重复的元素的个数。在 Java 中，使用 HashSet 比较方便，HashSet 的大小就是所求答案。具体实现代码如下，供参考。

通过代码

朴素解法

    public int minimumOperations(int[] nums) {        int ans = 0;        int n = nums.length;
        Arrays.sort(nums);        int k = 0;        while (!check(nums, n)) {            for (int j = k; j < n; j++) {                if (nums[j] != 0) {                    int temp = nums[j];                    nums[j] -= temp;                    j++;                    k = j;                    while (j < n && nums[j] != 0) {                        nums[j] -= temp;                        j++;                    }                }            }            ans++;        }                return ans;    }        private boolean check(int[] nums, int n) {        for (int i = 0; i < n; i++) {            if (nums[i] != 0) {                return false;            }        }        return true;    }

复制代码

HashSet 解法

    public int minimumOperations(int[] nums) {        Set<Integer> set = new HashSet<>();        for (int num : nums) {            if (num > 0) {                set.add(num);            }        }        return set.size();    }

复制代码