2626. 数组归约运算
2626. 数组归约运算
题目
Given an integer array nums
, a reducer function fn
, and an initial value init
, return the final result obtained by executing the fn
function on each element of the array, sequentially, passing in the return value from the calculation on the preceding element.
This result is achieved through the following operations: val = fn(init, nums[0]), val = fn(val, nums[1]), val = fn(val, nums[2]), ...
until every element in the array has been processed. The ultimate value of val
is then returned.
If the length of the array is 0, the function should return init
.
Please solve it without using the built-in Array.reduce
method.
Example 1:
Input:
nums = [1,2,3,4]
fn = function sum(accum, curr)
init = 0
Output: 10
Explanation:
initially, the value is init=0.
(0) + nums[0] = 1
(1) + nums[1] = 3
(3) + nums[2] = 6
(6) + nums[3] = 10
The final answer is 10.
Example 2:
Input:
nums = [1,2,3,4]
fn = function sum(accum, curr) { return accum + curr * curr; }
init = 100
Output: 130
Explanation:
initially, the value is init=100.
(100) + nums[0] * nums[0] = 101
(101) + nums[1] * nums[1] = 105
(105) + nums[2] * nums[2] = 114
(114) + nums[3] * nums[3] = 130
The final answer is 130.
Example 3:
Input:
nums = []
fn = function sum(accum, curr)
init = 25
Output: 25
Explanation: For empty arrays, the answer is always init.
Constraints:
0 <= nums.length <= 1000
0 <= nums[i] <= 1000
0 <= init <= 1000
题目大意
给定一个整数数组 nums
、一个 reducer 函数 fn
和一个初始值 init
,返回通过依次对数组的每个元素执行 fn
函数得到的最终结果。
通过以下操作实现这个结果:val = fn(init, nums[0]),val = fn(val, nums[1]),val = fn(val, nums[2]),...
直到处理数组中的每个元素。然后返回 val
的最终值。
如果数组的长度为 0,则函数应返回 init
。
请你在不使用内置数组方法的 Array.reduce
前提下解决这个问题。
示例 1:
输入:
nums = [1,2,3,4]
fn = function sum(accum, curr)
init = 0
输出: 10
解释:
初始值为 init=0 。
(0) + nums[0] = 1
(1) + nums[1] = 3
(3) + nums[2] = 6
(6) + nums[3] = 10
Val 最终值为 10。
示例 2:
输入:
nums = [1,2,3,4]
fn = function sum(accum, curr) { return accum + curr * curr; }
init = 100
输出: 130
解释:
初始值为 init=100 。
(100) + nums[0]^2 = 101
(101) + nums[1]^2 = 105
(105) + nums[2]^2 = 114
(114) + nums[3]^2 = 130
Val 最终值为 130。
示例 3:
输入:
nums = []
fn = function sum(accum, curr)
init = 25
输出: 25
解释: 这是一个空数组,所以返回 init 。
提示:
0 <= nums.length <= 1000
0 <= nums[i] <= 1000
0 <= init <= 1000
解题思路
这道题主要考察如何实现 reduce
函数,模拟 JavaScript 内置的 Array.prototype.reduce
方法,逐一处理数组中的元素并将其与当前聚合值结合,最终返回聚合的结果,其关键在于遍历数组并不断更新聚合值,操作非常常见,尤其在处理数据时常用于累加、最大最小值计算等场景。
- 初始化结果:将
init
作为初始的聚合值res
。 - 遍历数组:从数组的第一个元素开始,依次将当前聚合值
res
和数组元素nums[i]
传入回调函数fn
,并将fn
返回的结果作为新的聚合值。 - 返回结果:遍历结束后,返回聚合后的最终值。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是数组nums
的长度,需要遍历整个数组,每个元素执行一次fn
操作。 - 空间复杂度:
O(1)
,因为只需要常量空间来存储聚合结果和计数器。
代码
/**
* @param {number[]} nums
* @param {Function} fn
* @param {number} init
* @return {number}
*/
var reduce = function (nums, fn, init) {
let res = init;
for (let i = 0; i < nums.length; i++) {
res = fn(res, nums[i]);
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
2631 | 分组 | [✓] | ||
2634 | 过滤数组中的元素 | [✓] | ||
2635 | 转换数组中的每个元素 | [✓] |