Range Addition解题报告

Description:

Assume you have an array of length n initialized with all 0's and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

Example:

Example:

Given:

length = 5,
updates = [
    [1,  3,  2],
    [2,  4,  3],
    [0,  2, -2]
]

Output:

[-2, 0, 3, 5, 3]

Explanation:

Initial state:
[ 0, 0, 0, 0, 0 ]

After applying operation [1, 3, 2]:
[ 0, 2, 2, 2, 0 ]

After applying operation [2, 4, 3]:
[ 0, 2, 5, 5, 3 ]

After applying operation [0, 2, -2]:
[-2, 0, 3, 5, 3 ]

Link:

https://leetcode.com/problems/range-addition/description/

解题方法:

除了直接按照题意暴力破解,还有一种使用加法结合律的方法,以以上例子为例:
当有只有一个命令:[1, 3, 2]

  • 操作1
    start位置进行+= 2的操作,在end+1的位置进行-=2的操作。
  • 操作2
    当我们遍历整个数组进行a[i] += a[i - 1]的操作时,即可得到我们想要的数组。

这道题所有的操作都是加法,所以不管有多少个命令,我们都先进行操作1,然后再最后统一进行操作2,即可得到所求的数组。

Tips:

O(length + updates.size())

Time Complexity:

完整代码:

vector<int> getModifiedArray(int length, vector<vector<int>>& updates) 
    {
        vector<int> result(length);
        for(auto a: updates)
        {
            result[a[0]] += a[2];
            if(a[1] + 1 < length)
                result[a[1] + 1] -= a[2];
        }
        for(int i = 1; i < length; i++)
            result[i] += result[i - 1];
        return result;
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,792评论 0 33
  • 5、 我曾经深刻迷恋的你,哪怕只有那么一个月,一天,一个小时,或者一分一秒, 或者没有结局甚至没有开始,但至少,我...
    甜澈阅读 1,277评论 0 1
  • 美队3不出(多数友人的)意外让本来毫不期待的我十分满意,尤其是绝不磨叽纠结,亮明立场说打就打,打得干净利落漂亮直爽...
    方城主阅读 716评论 0 0
  • 1985年,贝佐斯第一次接触互联网。不过要到1994年贝佐斯才意识到它的商业潜力。那是什么年代呢?1994年,中国...
    kafkaliu阅读 177评论 0 0
  • 未完
    深沉的简单阅读 90评论 0 0