Java 中通过减去相等数量使数组变为零

2024 年 8 月 28 日 | 阅读 9 分钟

引言

给定一个整数数组，我们要使数组中的所有元素相等，并且需要用最少的步骤将数组元素减至零。

方法 1

使用暴力方法

Java 代码

import java.util.Arrays;
public class MakeArrayZeroBruteForce {
    public static void main(String[] args) {
        int[] nums = {1, 5, 0, 3, 5};
System.out.println("Original Array : " +  Arrays.toString(nums));
        int operations = makeArrayZero(nums);
       
System.out.println("Modified Array : " + Arrays.toString(nums));
       
System.out.println("Number of Operations : " + operations);
    }

    public static int makeArrayZero(int[] nums) {
        int operations = 0;
        while (!allElementsZero(nums)) {
            int min = Integer.MAX_VALUE;
            for (int num : nums) {
                if (num > 0) {
                    min = Math.min(min, num);
                }
            }
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > 0) {
                   
nums[i] -= min;
                }
            }
operations++;
        }
        return operations;
    }

    public static boolean allElementsZero(int[] nums) {
        for (int num : nums) {
            if (num != 0) {
                return false;
            }
        }
        return true;
    }
}

输出

Original Array : [1, 5, 0, 3, 5]
Modified Array : [0, 0, 0, 0, 0]
Number of Operations : 3

说明

MakeArrayZeroBruteForce 类包含 main 和 helper 方法：makeArrayZero 和 allElementsZero。
main 方法根据提供的输入初始化数组并打印其原始状态。然后，它调用 makeArrayZero 方法，该方法使用暴力方法将所有元素归零。之后，它打印修改后的数组以及所需的 the 操作次数。
makeArrayZero 方法反复地从所有正元素中减去最小正值，直到所有元素都归零。它使用一个 while 循环，只要元素不全为零，循环就会继续。
内部 for 循环查找数组中的最小正值。
另一个 for 循环将计算出的最小值从所有正元素中减去。
allElementsZero 方法检查数组中的所有元素是否为零。如果所有元素都为零，则返回 true，否则返回 false。

时间复杂度

外部 while 循环一直运行到所有元素都归零为止，这最多需要 max(nums) 步。
查找最小正值的内部 for 循环运行时间为 O(n)。
第二个 for 循环将最小值从所有正元素中减去，时间复杂度为 O(n)。
总的来说，这种暴力方法的 worst-case 时间复杂度为 O(n * max(nums))，其中 n 是数组中的元素数量。

空间复杂度

空间复杂度为 O(1)，因为算法使用的额外空间是恒定的，与输入大小无关。

代码的乾运行

输入：nums = [1, 5, 0, 3, 5]。

初始状态

nums = [1, 5, 0, 3, 5]

操作次数：0

第一次迭代

查找数组中的最小正值：min = 1
从所有正元素中减去 min
nums = [0, 4, 0, 2, 4]

操作次数：1

第二次迭代

查找数组中的最小正值：min = 2
从所有正元素中减去 min
nums = [0, 2, 0, 0, 2]

操作次数：2

第三次迭代

查找数组中的最小正值：min = 2
从所有正元素中减去 min
nums = [0, 0, 0, 0, 0]

操作次数：3

最终状态

nums = [0, 0, 0, 0, 0]
总操作次数：3

方法 2

使用优先队列

Java 代码

import java.util.*;
public class Solution {
    public int minimumOperations(int[] nums) {
        int ans = 0; 
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        
        while (true) {
            for (int i : nums) {
                if (i != 0)
                   
maxHeap.offer(i);
            }
            if (maxHeap.isEmpty()) {
                break;
            }
            int minEle = maxHeap.poll();
            
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != 0) {
                   
nums[i] = nums[i] - minEle;
                }
            }
            ans++;
            if (!maxHeap.isEmpty()) {    
maxHeap.clear();
            }
        }
        
        return ans;
    }
    
    public static void main(String[] args) {
        int[] nums = {1, 5, 0, 3, 5};
        Solution solution = new Solution();
        int output = solution.minimumOperations(nums);
       
System.out.println(" Minimum number of operations to make every element in nums equal to 0 is  : " + output); // Output : 3
    }
}

输出

 Minimum number of operations to make every element in nums equal to 0 is  : 3

说明

minimumOperations 方法接收一个数组 num 作为输入，旨在以最少的操作次数将数组中的所有元素减至零。代码使用最大堆（优先队列）来跟踪数组中的最大元素。
代码在每次迭代中遍历数组，并将所有非零元素添加到最大堆中。
添加元素后，检索最大元素（最大堆的顶部）并从数组中的所有非零元素中减去它。
循环一直持续到数组中的所有元素都归零为止。
ans 变量跟踪实现此目标所需的the 操作次数。

时间复杂度 :

while 循环一直运行到所有元素都归零为止，在每次迭代中，代码都会处理数组中的所有非零元素并对其执行操作。
最大迭代次数是数组中的最大元素 (max(nums))，这可以认为是 O(n)。
在 while 循环内部，最大堆操作（offer、poll、clear）的时间复杂度均为 O(log n)，其中 n 是最大堆中的元素数量。

空间复杂度

代码使用最大堆来存储非零元素，因此由于最大堆，空间复杂度为 O(n)。

代码的乾运行

nums = [1, 5, 0, 3, 5]。

初始状态

nums = [1, 5, 0, 3, 5]

ans = 0

迭代 1

将非零元素添加到最大堆：maxHeap = [5, 3, 5, 1]
从最大堆中 poll 出最大元素 (5)，并将其从所有非零元素中减去
nums = [1, 0, 0, 3, 0]
ans 加 1

迭代 2

将非零元素添加到最大堆：maxHeap = [3, 1]
从最大堆中 poll 出最大元素 (3)，并将其从所有非零元素中减去
nums = [1, 0, 0, 0, 0]
ans 加 1

迭代 3

将非零元素添加到最大堆：maxHeap = [1]
从最大堆中 poll 出最大元素 (1)，并将其从所有非零元素中减去
nums = [0, 0, 0, 0, 0]
ans 加 1
while 循环条件现在满足，迭代将停止。

最终状态

nums = [0, 0, 0, 0, 0]
ans = 3

方法 3

使用排序

Java 代码

import java.util.*;
class Solution {
    private void subtract(int[] nums, int  index, int value){
        for(int i  =  index;i<nums.length;i++){
            nums[i] -= value;
        }
    }

    public int minimumOperations(int[] nums) {
        int count = 0;
       
Arrays.sort(nums) ;
        
        for(int i = 0;i<nums.length;i++){
            if(nums[i]  > 0){
               
subtract(nums, i, nums[i]);
               
count++;
            }
        }
        return count;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 5, 0, 3, 5};
        Solution solution = new Solution();
        int output = solution.minimumOperations(nums);
       
System.out.println ("minimum number of operations to make every element in nums equal to 0 is :
:  " +  output); // Output : 3
    }
}

输出

minimum number of operations to make every element in nums equal to 0 is : 3

说明

Solution 类包含 solution 方法 minimumOperations 和一个 helper 方法 subtract。
subtract 方法接收一个 nums 数组、一个索引和一个值作为输入。它将提供的值从从指定索引开始的数组元素中减去。minimumOperations 方法旨在通过减去相等的值来使数组中的所有元素归零。它首先按升序对输入数组进行排序。
然后代码遍历排序后的数组。对于遇到的每个非零元素，它将其值从自身以及所有后续元素中减去。此操作表示从所有元素中减去最大值。
count 变量跟踪执行的操作次数。

时间复杂度

排序过程需要 O(n log n) 时间，其中 n 是数组条目数。
遍历排序后数组的循环在 worst-case 下以 O(n) 时间运行。
因此，整体时间复杂度由排序决定，为 O(n log n)。

空间复杂度

输入数组和 helper 变量定义了空间复杂度，导致 O(n) 的空间复杂度。

代码的乾运行

nums = [1, 5, 0, 3, 5]。

初始状态

nums = [1, 5, 0, 3, 5]
count = 0

排序步骤

排序后：nums = [0, 1, 3, 5, 5]

第一次迭代

当前元素：nums[0] = 0（已为零）
无需操作，移至下一个元素

第二次迭代

当前元素：nums[1] = 1
将 1 从所有右侧元素（索引 2 到 4）中减去
nums = [0, 0, 2, 4, 4]
count 加 1

第三次迭代

当前元素：nums[2] = 2
将 2 从所有右侧元素（索引 3 到 4）中减去
nums = [0, 0, 0, 2, 2]
count 加 1

第 4 次迭代

当前元素：nums[3] = 2
将 2 从所有右侧元素（索引 4）中减去
nums = [0, 0, 0, 0, 0]
count 加 1

迭代 5

所有元素都为零，循环终止

最终状态

nums = [0, 0, 0, 0, 0]
count = 3

方法 4

使用贪心算法

Java 代码

class Solution {
    public int minimumOperations(int[] nums) {
        int count = 0, n = nums.length, x = 0, ans = 0; 
        while(count < n) {
            int min = Integer.MAX_VALUE;
            count = 0;
            for(int i = 0; i < n; i++) {
               
if(nums[i] <= 0) count++;
                else {
nums[i] -= x;  
if(nums[i] <= 0) count++;    
else min = Math.min(nums[i], min);
                }
            }
            x = min;
            ans++;
        }
        return ans - 1;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 5, 0, 3, 5};
        Solution solution = new Solution();
        int output = solution.minimumOperations(nums);
        System.out.println("Minimum number of operations to make every element in nums equal to 0 is :  " + output); // Output: 3
    }
}

输出

Minimum number of operations to make every element in nums equal to 0 is : 3

说明

Solution 类包含 solution 方法 minimumOperations 和一个 helper 方法 subtract。
subtract 方法输入一个 nums 数组、一个索引和一个值。它将给定值从指定索引开始的数组元素中减去。
minimumOperations 函数通过减去相等的值来寻求将所有数组元素减至零。它首先按升序对输入数组进行排序。
然后代码遍历排序后的数组。对于遇到的每个非零元素，它将其值从自身以及所有后续元素中减去。此操作表示从所有元素中减去最大值。
count 变量跟踪执行的操作次数。

时间复杂度

排序操作需要 O(n log n) 时间，其中 n 是数组中的元素数量。
遍历排序后数组的循环以 O(n) 时间运行。
在循环内部，subtract 方法在 worst-case 下也以 O(n) 时间处理剩余元素。
因此，排序决定了整体时间复杂度，为 O(n log n)。

空间复杂度

输入数组和 helper 变量定义了空间复杂度，导致 O(n) 的空间复杂度。

方法 4

使用哈希集

Java 代码

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minimumOperations(int[] nums) {
       
Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            if (n > 0) {
set.add(n);
            }
        }
        return set.size();
    }
}
public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 5, 0, 3, 5};
        Solution solution = new Solution();
        int output = solution.minimumOperations(nums);
       
System.out.println("Output: " + output); // Output: 3
    }
}

输出

Output: 3

说明

Solution 类包含 solution 方法 minimumOperations。该解决方案依赖于这样一个观察：将所有元素减至零所需的最小操作次数等于数组中不同正元素的数量。
代码初始化一个名为 set 的 HashSet 来跟踪不同的正元素。循环遍历数组中的每个元素。如果元素为正 (n > 0)，则将其添加到集合中。
处理完所有元素后，返回集合的大小作为结果。此大小表示将所有元素减至零所需的最小操作次数。

时间复杂度

循环遍历数组中的所有元素一次。
假设有一个好的哈希函数，将元素添加到哈希集中平均时间复杂度为 O(1)。
整体时间复杂度为 O(n)，其中 n 是数组中的元素数量。

空间复杂度

空间复杂度为 O(k)，其中 k 是数组中不同正元素的数量。
在 worst-case 下，当所有正元素都不同时，空间复杂度可能为 O(n)。

下一个主题最大和对等于最高数字

Java 中通过减去相等数量使数组变为零

引言

方法 1

使用暴力方法

方法 2

使用优先队列

方法 3

使用排序

方法 4

使用贪心算法

方法 4

使用哈希集

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

Java 中通过减去相等数量使数组变为零

引言

方法 1

使用暴力方法

方法 2

使用优先队列

方法 3

使用排序

方法 4

使用贪心算法

方法 4

使用哈希集

相关帖子

DSA 中的外星人词典问题

Y 型链表的交点

检查一个队列是否可以使用一个栈排序到另一个队列

从字符流中查找第一个非重复字符

查找范围 L 到 R 中大于 K 的元素数量 (离线查询)

半结构化数据

B+ 树插入

计数排序 vs 桶排序

有效井字棋棋盘配置的有效性

二叉树的简洁编码

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器