How to Compute Running Sum of 1d Array using std::partial_sum in

  • 时间:2020-09-08 11:19:41
  • 分类:网络文摘
  • 阅读:104 次

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]). Return the running sum of nums.

Example 1:
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2:
Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3:
Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

Constraints:
1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6

Hints:
Think about how we can calculate the i-th number in the running sum from the (i-1)-th number.

Accumulate Prefix Sum

A traditional approach to compute the running sum would be to accumulate the prefix sum. You can use an additional variable to keep the sum, or simply we can update in place (use previous element in the array) to store the prefix sum.

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++ i) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
};
class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++ i) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
};

C++ std::partial_sum

The C++ std::partial_sum does exactly this job. The function computes the partial sums of the elements in the range specified by [first, last) and update them to the range begining at third parameter.

1
2
3
4
5
6
7
class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        partial_sum(begin(nums), end(nums), begin(nums));
        return nums;
    }
};
class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        partial_sum(begin(nums), end(nums), begin(nums));
        return nums;
    }
};

The std::partial_sum may be implemented as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<class InputIt, class OutputIt>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, 
                     OutputIt d_first)
{
    if (first == last) return d_first;
 
    typename std::iterator_traits<inputit>::value_type sum = *first;
    *d_first = sum;
 
    while (++first != last) {
       sum = std::move(sum) + *first; // std::move since C++20
       *++d_first = sum;
    }
    return ++d_first;
 
    // or, since C++14:
    // return std::partial_sum(first, last, d_first, std::plus<>());
}
template<class InputIt, class OutputIt>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, 
                     OutputIt d_first)
{
    if (first == last) return d_first;
 
    typename std::iterator_traits<inputit>::value_type sum = *first;
    *d_first = sum;
 
    while (++first != last) {
       sum = std::move(sum) + *first; // std::move since C++20
       *++d_first = sum;
    }
    return ++d_first;
 
    // or, since C++14:
    // return std::partial_sum(first, last, d_first, std::plus<>());
}

The loops can be unrolled as the following:

1
2
3
4
5
*(d_first)   = *first;
*(d_first+1) = *first + *(first+1);
*(d_first+2) = *first + *(first+1) + *(first+2);
*(d_first+3) = *first + *(first+1) + *(first+2) + *(first+3);
...
*(d_first)   = *first;
*(d_first+1) = *first + *(first+1);
*(d_first+2) = *first + *(first+1) + *(first+2);
*(d_first+3) = *first + *(first+1) + *(first+2) + *(first+3);
...

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
How to Do Email Marketing in 2020: A Beginner’s Guide  5 Music Blogs That Are Rocking It And How To Get Your Own Band F  Depth First Search Algorithm with Hash Set to Find Elements in a  Algorithms to Count How Many Numbers Are Smaller Than the Curren  Finding the Closest Divisors  Greedy Solution to Reconstruct a 2-Row Binary Matrix  How to Use jOOQ Library to Write SQL in Java using Fluent Style?  Algorithm to Compute the Number of Days Between Two Dates  How to Sort Integers by The Number of 1 Bits?  Using Depth First Search Algorithm to Delete Tree Nodes with Sum 
评论列表
添加评论