Leetcode: Range Addition

发布时间:2017-6-29 1:35:17 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Leetcode: Range Addition ",主要涉及到Leetcode: Range Addition 方面的内容,对于Leetcode: Range Addition 感兴趣的同学可以参考一下。

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: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 ]Hint:

Time Complexity: O(N+K), Space: O(1)

  1. For each update operation, do you really need to update all elements between i and j?
  2. Update only the first and end element is sufficient.
  3. The optimal time complexity is O(k + n) and uses O(1) extra space.
 1 public class Solution { 2     public int[] getModifiedArray(int length, int[][] updates) { 3         int[] res = new int[length]; 4         for (int[] update : updates) { 5             res[update[0]] += update[2]; 6             if (update[1]+1 < length) res[update[1]+1] -= update[2]; 7         } 8         for (int i=1; i<length; i++) { 9             res[i] = res[i] + res[i-1];10         }11         return res;12     }13 }

上一篇:bash{} 方法总结
下一篇:Network (poj1144)

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。