0 offer : 腾讯云智也是腾讯，运营开发也是开发

宫水三叶的刷题日记

发布于 2024-05-13 16:42:56

1570

发布于 2024-05-13 16:42:56

文章被收录于专栏：宫水三叶的刷题日记宫水三叶的刷题日记

回归主线。

五一假期，给大家安排一些「难度不大」的算法题。

题目描述

平台：LeetCode

题号：1785

给你一个整数数组 nums，和两个整数 limit 与 goal。

数组 nums 有一条重要属性：abs(nums[i]) <= limit。

返回使数组元素总和等于 goal 所需要向数组中添加的最少元素数量，添加元素不应改变数组中 abs(nums[i]) <= limit 这一属性。

注意，如果 x >= 0，那么 abs(x) 等于 x ；否则，等于 -x。

示例 1：

输入：nums = [1,-1,1], limit = 3, goal = -4

输出：2

解释：可以将 -2 和 -3 添加到数组中，数组的元素总和变为 1 - 1 + 1 - 2 - 3 = -4 。

示例 2：

输入：nums = [1,-10,9,1], limit = 100, goal = 0

输出：1

提示：

1 <= nums.length <= 10^5

1 <= limit <= 10^6

-limit <= nums[i] <= limit

-10^9 <= goal <= 10^9

贪心

对于 nums 而言，我们可以先通过

O(n)

的遍历求得其原总和 sum 为何值。

若 sum 与 goal 不等，我们可以按照「贪心」的方式里添加元素。

由于添加的元素需要满足 abs(x) <= limit 要求，因此我们添加数的范围在

[-limit, limit]

之间。

为确保添加的元素最小，我们应当优先添加能够有效抵消两者差值的数值（添加

limit

或

-limit

），添加个数为

\left \lceil \frac{\left | sum - goal \right |}{limit} \right \rceil

。

Java 代码：

class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        long sum = 0;
        for (int x : nums) sum += x;
        return (int) ((Math.abs(sum - goal) + limit - 1) / limit);
    }
}

TypeScript 代码：

function minElements(nums: number[], limit: number, goal: number): number {
    let sum = 0
    for (const x of nums) sum += x
    return Math.ceil(Math.abs(sum - goal) / limit)
}

Python 代码：

class Solution:
    def minElements(self, nums: List[int], limit: int, goal: int) -> int:
        sumv = sum(nums)
        return (abs(sumv - goal) + limit - 1) // limit