leetcode
leetcode 2301 ~ 2350
使数字变为非正数的最小操作次数

使数字变为非正数的最小操作次数

难度:

标签:

题目描述

代码结果

运行时间: 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`作为搜索范围的上界?是否有可能存在更小的搜索范围?
选择`max(nums) // y + 1`作为搜索范围的上界是因为在最极端的情况下,即每次操作只减去`y`而不使用`x-y`的情况下,要使最大的数字变为非正数至少需要`max(nums) // y`次操作。加1是因为二分查找的范围需要覆盖可能的边界情况。理论上,这是一个保守的估计,实际上可能存在更小的`k`值,因为在一些情况下使用`x-y`操作可以更高效地减少数字,从而减少操作次数。这是初步设定的上界,二分查找将在这个范围内找到实际的最小`k`。
🦆
在`check`函数中,为什么在每个数字减去`k*y`后,仅当数值仍然大于0时才考虑进一步的`x-y`操作?如果`x-y`为负数如何处理?
在`check`函数中,只有当数字减去`k*y`后仍然大于0时,才需要进一步考虑使用`x-y`操作,因为如果数字已经非正,则不需要进一步操作。如果`x-y`为负数,实际上这种情况在题目设定中不应存在,因为这会使问题变得无意义(即无法通过减去一个负数使数字变小)。通常,我们假定`x > y`以确保`x-y`为正,从而使得每次操作都有效地减少数字。
🦆
在`check`函数中计算`x-y`操作次数时,使用的是`(a - 1) // (x - y) + 1`,这种计算方式是否能正确处理所有情况,特别是当`a`正好是`x-y`的倍数时?
使用`(a - 1) // (x - y) + 1`的计算方式是为了处理任何正整数`a`的情况,确保能够正确计算出将`a`减至0或以下所需的最小操作次数。当`a`正好是`x-y`的倍数时,这种计算方式依然有效。例如,如果`a = (x-y) * 2`,那么`(a - 1) // (x - y) + 1`计算结果将是3,但由于我们是从`a-1`开始计算的,所以实际上我们只需要2次操作,这正符合预期的结果。
🦆
在题解中没有提到`x`、`y`的相对大小,`x`小于`y`的情况下,题解的逻辑是否还适用?
如果`x`小于`y`,题解中的逻辑将不适用,因为在这种情况下,`x-y`将是负数,这意味着操作会增加数字而不是减少,与题目要求相矛盾。题解假设`x > y`以确保每次操作都能有效地减少数值。如果`x < y`,则需要重新考虑问题的设定和解决方案。

相关问题