回归主线。
五一假期,给大家安排一些「难度不大」的算法题。
题目描述
平台:LeetCode
题号:1785
给你一个整数数组 nums
,和两个整数 limit
与 goal
。
数组 nums
有一条重要属性:abs(nums[i]) <= limit
。
返回使数组元素总和等于 goal
所需要向数组中添加的 最少元素数量 ,添加元素 不应改变 数组中 abs(nums[i]) <= limit
这一属性。
注意,如果 x >= 0
,那么 abs(x)
等于 x
;否则,等于 -x
。
示例 1:
代码语言:javascript
复制
输入:nums = [1,-1,1], limit = 3, goal = -4
输出:2
解释:可以将 -2 和 -3 添加到数组中,数组的元素总和变为 1 - 1 + 1 - 2 - 3 = -4 。
示例 2:
代码语言:javascript
复制
输入:nums = [1,-10,9,1], limit = 100, goal = 0
输出:1
提示:
贪心
对于 nums
而言,我们可以先通过
的遍历求得其原总和 sum
为何值。
若 sum
与 goal
不等,我们可以按照「贪心」的方式里添加元素。
由于添加的元素需要满足 abs(x) <= limit
要求,因此我们添加数的范围在
之间。
为确保添加的元素最小,我们应当优先添加能够有效抵消两者差值的数值(添加
或
),添加个数为
。
Java 代码:
代码语言:javascript
复制
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 代码:
代码语言:javascript
复制
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 代码:
代码语言:javascript
复制
class Solution:
def minElements(self, nums: List[int], limit: int, goal: int) -> int:
sumv = sum(nums)
return (abs(sumv - goal) + limit - 1) // limit
- 时间复杂度:
- 空间复杂度: