RangeAddition [source code]
public class RangeAddition {
static
/******************************************************************************/
public class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] nums = new int[length];
for (int[] update : updates) {
int start = update[0], end = update[1], val = update[2];
nums[start] += val;
if (end + 1 < length)
nums[end + 1] -= val;
}
for (int i = 1; i < length; i++)
nums[i] += nums[i - 1];
return nums;
}
}
/******************************************************************************/
public static void main(String[] args) {
RangeAddition.Solution tester = new RangeAddition.Solution();
int[][][] inputs = {
{{5}}, {{1, 3, 2},
{2, 4, 3},
{0, 2, -2}}, {{-2, 0, 3, 5, 3}},
};
for (int i = 0; i < inputs.length / 3; i++) {
int length = inputs[3 * i][0][0];
int[][] updates = inputs[1 + 3 * i];
int[] expected = inputs[2 + 3 * i][0];
String inputStr = length + " AND \n" + Matrix.printMatrix(updates);
String expectedStr = Printer.array(expected);
int[] output = tester.getModifiedArray(length, updates);
String outputStr = Printer.array(output);
System.out.println(Printer.seperator());
System.out.println(Printer.wrapColor(inputStr, "magenta") + " -> " + outputStr + Printer.wrapColor(", expceted: " + expectedStr, outputStr.equals(expectedStr) ? "green" : "red"));
}
}
}
这题的笨办法肯定就是挨个加. 这个是一个Google的题目, 所以这种办法肯定是不可能被接受的;
这题不应该看hint的, 看完了基本上主要思路就知道了. 这个题目基本其实就一个悬念, hint里面看到了就没了;
如果从思想上来看, 这个题目用到的一个思考方式就是directly envision the result, 也就是直接考虑我们操作完了最后的结果是什么样的;
另外就是举例升级的思路: 这题我们首先最简单的例子就是, 我们只考虑inc是正数的情况; 其次, 我们从假如只有两个operation的情况来开始考虑, 然后要么脑子里要么手动, visualize起来; 然后分析在这样一个简单的例子下面, 笨办法是什么, 然后你能总结出什么聪明的更好的办法?
这个题目还是比我想的要复杂很多, 本来以为如果知道hint里面说的两个端点的话, 这个题目的大体思路就有了, 但是实际上完全不是这样, 就算能够把这个点get到, 实际上要转换成最后的输出, 还有一个关键点, 就是怎么通过这些端点的值来判断其他点的值. 我这一次又是陷入到了历史信息流算法的套路里面, 最后还是没有办法写出一个正确的逻辑. 这个是我的错误的代码:
public class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] nums = new int[length];
for (int[] update : updates) {
int inc = update[2];
nums[update[0]] += inc;
nums[update[1]] += inc;
}
Integer start = null, prev = null;
for (int i = 0; i < length; i++) {
if (nums[i] != 0) {
if (start == null) {
start = i;
prev = nums[i];
} else if (prev * nums[i] < 0) {
start = i;
prev = nums[i];
} else {
int paint = Math.min(Math.abs(prev), Math.abs(nums[i]));
paint(nums, start, i - 1, paint);
start = i;
prev = nums[i];
}
}
}
return nums;
}
public void paint(int[] nums, int start, int end, int paint) {
for (int i = start; i <= end; i++)
nums[i] = paint;
}
}
看了一下editorial的答案, 这个题目好像其实比我想象的复杂很多. 首先, 这一个题目再次印证了一个之前的教训: 当我拘泥于历史信息流算法但是却做不出来的时候, 真正能够解决这个题目的往往是一个simple intuition. 这个题目我就是没有想到这个intuition, 所以最后也是没办法做出来;
上面的代码是看editorial看来的, 这个是submission上面看到的另外一个代码:
public class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] res = new int[length];
for(int[] t : updates){
int s = t[0];
int e = t[1];
int v = t[2];
res[s] += v;
if(e < length - 1){
res[e+1] -= v;
}
}
int sum = 0;
for(int i=0;i<length;i++){
sum+= res[i];
res[i] = sum;
}
return res;
}
}
这个代码相对来说更有利于理解这个题目背后的思想;
如果想要细致的看, 可以看editorial的article: https://leetcode.com/articles/range-addition/
简单来说, 这个解法的核心思路就是重新定义了range increment这个概念. 这个redefinition的过程其实有点类似于我们算path sum III 的时候的一个思路, 用Complement的思路来做. 与其认为一个update是在[start..end]这个范围上做一个increment, 不如说其实是在[start: ]的范围上做一个+val的操作, 在[end+1: ]的范围上做一个-val的操作: 这样一个redefinition实际最后得到的效果等价于让only [start..end] + val([end+1:]上的-val其实等价于将前面的+val 给cancel out).
当然这样的一个redefinition其实是为了和后面的操作对应起来的. 这样一个stream化的重新定义, 就导致后面计算每一个entry所收到的interval的影响的时候就方便很多. 当你站在一个entry的位置的时候, 你要考虑的只有你左边, 有多少个位置给你发射过+/-val的 influence steam. 这里这个submission代码的思路就是这样做的, 直接用一个sum来计算每一个位置对应的influence stream的数量之和, 然后将这个和直接给当前的entry就行了;
当然, 如editorial上面的做法所展示的一样, 这样的逻辑还可以进一步简化一点, 就是用一个类似DP的思路理解: [i-1]的entry已经cover了所有的[:i-1]的influence, 所以你站在[i]只要考虑[i-1]有什么influence就行了;
这里就可以看到, 这里前面的这个process updates的过程的操作方式, 跟最后collect的过程的操作方式之间是相辅相成的.
这个是editorial上面给出的intuition:
Intuition
- There is only one read query on the entire range, and it occurs at the end of all update queries. Additionally, the order of processing update queries is irrelevant.
- Cumulative sums or partial_sum operations apply the effects of past elements to the future elements in the sequence.
以及:
It is good to note that this works for multiple update queries because the particular binary operations here (namely addition and subtraction):
- are closed over the entire domain of Integers. (A counter example is division which is not closed over all Integers).
- are complementary operations. (As a counter example multiplication and division are not always complimentary due to possible loss of precision when dividing Integers).
然后还有这个问题的Follow-Up:
An extension of this problem is to apply such updates on an array where all elements are not the same.
In this case, the second approach requires that the original configuration must be stored separately before applying the final transformation. This incurs an additional space complexity of O(n).
@StefanPochmann suggested another method which does not require extra space, but requires an extra linear pass over the entire array. The idea is to apply reverse partial_sum operation on the array (for example, array [2,3,10,5] transforms to [2,1,7,−5]) as an initialization step and then proceed with the second method as usual.
stefan这个点子也是非常的牛逼; 但是这个Follow-Up本身并不难, 大体的思路就是你要找到的是updates所equivalanetly代表的influence stream的结果; 这两种做法的区别就是一个tradeoff, 要么是O(N) space, 要么是O(N) time.
Another general, more complex version of this problem comprises of multiple read and update queries over ranges. Such problems can be solved quite efficiently with Segment Trees by applying a popular trick called Lazy Propogation.
这个东西暂时没看了, 不过看来背后是有强力的理论支撑的. 放到notes里面去了; 有空可以去看看;
discussion有不少人说看这个答案都看不懂, 我起码看了一下之后立刻就理解了这个思路了, 说明我还是不算太笨的. 也有可能是因为我之前对于Complement这个概念已经强化记忆了几次了;
这个是一个理解:
Great solution. Though the code looks simple enough, it took me some time to figure out why exactly we do what we do here. We update the value at start index, because it will be used in the future when we are adding up the values for the sum at each index between start index and end index (both inclusive). We update the negative value at the end index + 1, because the positive value of it should be only added at its previous indices (from start index to end index). Thus, when we accumulate the sum at the end for each index, we will get the correct values for each index. If the end index is the last index in the resulting array, we don't have to do the end index + 1 part, because there is no more index after the last index and there will be no error when we accumulate the sum. Hope I explain it well enough to help others understand!
另外一个:
I think this idea initially derives from Binary Index Tree update/find operation:
// binary index tree
public int[] getModifiedArrayBinaryTree(int length, int[][] updates) {
if (length == 0) return new int[0];
int[] root = new int[length];
for (int[] update: updates) {
updateTree(root, update[1]+1, update[2]);
updateTree(root, update[0], -update[2]);
}
for (int i = 0; i < length; i++) {
root[i] = getValue(root, i+1, length);
}
return root;
}
private void updateTree(int[] root, int i, int value){
while (i > 0) {
root[i-1] += value;
i -= (i&(-i));
}
}
private int getValue(int[] root, int i, int n) {
int res = 0;
while (i <= n) {
res += root[i-1];
i += (i&(-i));
}
return res;
}
这个没看懂什么意思, 也许是一个我还没有见过的算法;
stefan认为, 其实这个题目整个就是历史信息流的问题, 只不过as to what to store and what to read的定义有些复杂:
@IWantToPass A slightly harder one is Meeting Rooms II and a significantly harder one is The Skyline Problem.
Let me describe the technique in my own words:
Go from the left end to the right end, holding some current status and update that status at certain points. For example in this problem, the status is the current array value. If the input has no operations, then you just walk from start to end and write "0" everywhere. But what if there's one operation, [startIndex=100, endIndex=200, inc=33]? Then you only write "0" until index 100, then you write "33" until index 200, and then you write "0" until the end. In other words, you start off writing "0", until something happens. You encounter the beginning of an operation. So you increase your status to "33" and keep writing that. Until the next event, which in this case is the end of that operation, so you decrease your status by 33 back to "0" and then keep writing that until the end.
The first half of xuyirui's solution (and pretty much everybody's, because it's the common and obvious way to do it) collects all these events, storing at what points we'll change the "current status value" and how we'll change it. And then the second half of the solution just does the walk, updating the "current status value" with the collected event data, and storing it in the output.
Would IMHO be a little clearer to go forwards and to use a separate array for the events data, which could also have a more appropriate name, like "increaseBy". (Then it's of course it's not O(1) extra space anymore, but that wasn't required, and it's also really not hard to go from separate array to reused array.)
所以这个问题我到底有没有拘泥于历史信息流的窠臼呢? 还是其实只是我自己没有做出来而已. 其实如果知道这个redefinition, 或许还是能想到这个历史信息流算法的, 不过就是这么一个关键点没有想到, 最后整个算法就一点思路都没有.
应该说我之前写过的几个历史信息流算法其实都比较简单的, 要么就是分段, counts, frequencies之类的, 多数都是比较简单的历史信息流的使用; 这个题目算是比较开眼, 属于历史信息流算法高阶的应用了. 很多时候核心问题就在于, 你的这个历史信息, 到底是什么(当问题要求的历史信息不再仅仅是counts, inRun之类这种简单的历史信息的时候);
还有一个目前为止做过比较复杂的历史信息流就是NGE, 当时也是想了半天;
这么一想, 这些东西里面其实也是有一个consistency在里面的: 这个题目要求的就是O(N)时间, 这个我们之前总结的时候就说, 一个技巧就是做一个历史信息流算法出来. 这里的这个历史信息流虽然比较难做, 不过仍然是这个思想的一个体现;
很多人其实都用电信号处理的思考方式来理解这个问题:
In a signal processing way of thinking...
Your output array is like a function f(x) = f1(x) + f2(x) + ... + fn(x) where x is the index.
where fi(x) is a modification to the array with a format like [0 0 0 ... k k k ... 0 0 0]
So taking fi(x) 's differentiation you get [0 0 0 +k 0 0 0 ... -k 0 0 0 ] where the -k locates at one behind the stopping index. (Pulses !!)
f'(x) = f1'(x) + f2'(x) + ... + fn'(x) which gets you the array in which you "only apply the update to the start and end indexes".
So applying an integral on f'(x), you get the result array.
Miss the old days thinking EE stuff.
这个是一个比较奇葩的解:
Sort the intervals with start first, use a heap (use end as compare) to maintain current valid intervals while iterating the result array.
public class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] res = new int[length];
List<int[]> list = new ArrayList<>();
for (int[] update : updates) list.add(update);
Collections.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
PriorityQueue<int[]> q = new PriorityQueue<int[]>(10, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});
int index = 0, sum = 0;
for (int i = 0; i < length; i++) {
while (index < list.size() && list.get(index)[0] == i) {
sum += list.get(index)[2];
q.offer(list.get(index++));
}
while (!q.isEmpty() && q.peek()[1] < i) {
sum -= q.poll()[2];
}
res[i] = sum;
}
return res;
}
}
作者声称是NlgK. 大概看了一下, 感觉其实还是一个穷加. 光是一个sort就已经是KlgK. 这个问题最后希望你从NK优化到N+K其实可能的一个原因就是因为K很大, 这个也属于符合实际的情形. 所以他这个算法其实未必能够做到真正的大幅度的加速;
不过了解这样一个加速的技巧还是有帮助的. 这个后面有空的时候再看一下, 这会儿有点没耐心看了;
另外他这个利用sort来降低难度, 这个其实也是属于array问题的一种常见思路;
Problem 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:
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 ]
Credits:
Special thanks to @vinod23 for adding this problem and creating all test cases.
Difficulty:Medium
Total Accepted:11.8K
Total Submissions:21.3K
Contributor: LeetCode
Companies
google
Related Topics
array
Similar Questions
Range Addition II
Hide Hint 1
Thinking of using advanced data structures? You are thinking it too complicated.
Hide Hint 2
For each update operation, do you really need to update all elements between i and j?
Hide Hint 3
Update only the first and end element is sufficient.
Hide Hint 4
The optimal time complexity is O(k + n) and uses O(1) extra space.