LeetCode（Heap)2357. Make Array Zero by Subtracting Equal Amounts

左手的ㄟ右手 2023-09-24 23:22 8阅读 0赞

# 1.问题 #

You are given a non-negative integer array nums. In one operation, you must:

Choose a positive integer x such that x is less than or equal to the smallest non-zero element in nums.  
Subtract x from every positive element in nums.  
Return the minimum number of operations to make every element in nums equal to 0.

Example 1:

> Input: nums = \[1,5,0,3,5\]  
> Output: 3  
> Explanation:  
> In the first operation, choose x = 1. Now, nums = \[0,4,0,2,4\].  
> In the second operation, choose x = 2. Now, nums = \[0,2,0,0,2\].  
> In the third operation, choose x = 2. Now, nums = \[0,0,0,0,0\].

Example 2:

> Input: nums = \[0\]  
> Output: 0  
> Explanation: Each element in nums is already 0 so no operations are needed.

Constraints:

*  1 <= nums.length <= 100
 *  0 <= nums\[i\] <= 100

# 2. 解题思路 #

## 方法1： ##

> 最少操作次数，数组中非0元素的个数，我们定义一个哈希表记录数组中不同元素的个数，最后相加

## 方法2： ##

> 1.数组排序，定义int变量result，sub  
> 2.for循环遍历，在减去元素不为零然后将sub添加，减去sub并result的次数

# 3. 代码 #

## 代码1： ##

HashMap<Integer, Integer> map = new HashMap<>();
        for(int n:nums){
        
            if (n!=0){
        
                map.put(n,0);
            }
        }
        return mp.size();

> 两者解题思路基本相同

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

## 代码2： ##

public int minimumOperations(int[] nums) {
        
            Arrays.sort(nums);//排序
            int result=0;//定义次数为result
            int sub=0;//减去的元素大小
    
            for (int i = 0; i < nums.length; i++) {
        //for循环遍历，在减去元素不为零然后将sub添加，减去sub并result的次数
                nums[i] = nums[i] - sub;
                if(nums[i]!=0){
        
                    sub+=nums[i];
                    result++;
                }
            }
            return result;
        }

> 解题思路基本相同，不同的是用优先队列，优先队列的好处是数组元素自动从小到大排序，弹出的头部元素是最小值

class Solution {
        
       public int minimumOperations(int[] nums) {
        
          PriorityQueue<Integer> pq = new PriorityQueue<>();//1.新建优先队列，nums数组元素如果不为0.存入
            for (Integer n: nums)
                if (n != 0)
                    pq.offer(n);//添加元素
    
            int prev = 0;//定义pre初始为0，目的是头部元素的值累计相加，数组元素减去prev，直到出现0
            int result = 0; //次数
            while (pq.size() > 0) {
        //循环，pq的长度大于0，弹出头部元素，nums数组元素减去prev
                int top = pq.poll();//弹出头部元素
                top -= prev;
    
                if (top <= 0) continue;
    
                prev += top;
                result++;
            }
    
            return result;
       }
    }

class Solution {
        
        public int minimumOperations(int[] nums) {
        
             PriorityQueue<Integer> pq = new PriorityQueue<>();
            int oper = 0;
            int result = 0;
    
            for (int item : nums)
                pq.add(item);
    
            while (!pq.isEmpty()) {
        
                int current = pq.poll();
    
                if (current <= result)
                    continue;
    
                oper++;
                result = current;
            }
    
            return result;
        }
    }