使数字变为非正数的最小操作次数
难度:
标签:
题目描述
代码结果
运行时间: 460 ms, 内存: 30.3 MB
/*
* 题目思路:
* 给定一个整数数组nums,我们需要将其变为非正数的最小操作次数。每次操作可以选择一个元素,将其减少1。
* 我们只需统计数组中所有正数的总和即为最小操作次数,因为每个正数都需要操作到0或负数。
*/
import java.util.Arrays;
public class Solution {
public int minOperations(int[] nums) {
return Arrays.stream(nums)
.filter(num -> num > 0)
.sum();
}
}
解释
方法:
此题解使用了二分查找和贪心算法的结合。首先,定义一个内部函数 check(k),该函数用于检查是否可以通过至多 k 次操作将所有数字减至不大于 0。在每次操作中,可以选择将任一数字减去 y 或 x-y(如果 x>y)。函数 check 遍历每个数字,首先将数字减去 k*y,然后根据剩余的正数部分计算需要多少次 x-y 的减法操作,如果总操作次数超过 k,则返回 False。主函数中,使用二分查找确定最小的满足条件的 k 值,即查找第一个使 check 函数返回 True 的 k 值。
时间复杂度:
O(n log(max(nums)/y))
空间复杂度:
O(1)
代码细节讲解
🦆
在使用二分查找方法时,为什么选择`max(nums) // y + 1`作为搜索范围的上界?是否有可能存在更小的搜索范围?
▷🦆
在`check`函数中,为什么在每个数字减去`k*y`后,仅当数值仍然大于0时才考虑进一步的`x-y`操作?如果`x-y`为负数如何处理?
▷🦆
在`check`函数中计算`x-y`操作次数时,使用的是`(a - 1) // (x - y) + 1`,这种计算方式是否能正确处理所有情况,特别是当`a`正好是`x-y`的倍数时?
▷🦆
在题解中没有提到`x`、`y`的相对大小,`x`小于`y`的情况下,题解的逻辑是否还适用?
▷