一維差分陣列
假設給你一個陣列 nums ，先對區間 [a,b] 中每個元素加 3 ，在對區間 [c,d] 每個元素減 5 …… ，這樣非常頻繁的區間修改，常規的做法可以一個個計算，
public void increment(int[] nums, int a, int b, int k) {
for (int index = a; index <= b; index++) {
nums[index] += k;
}
}
頻繁對陣列的一段區間進行增加或減去同一個值，如果一個個去操作，很明顯效率很差，我們可以使用差分陣列，差分陣列就是原始陣列相鄰元素之間的差，定義差分陣列 d[n] ，我們可以得到： d[i] = nums[i] ? nums[i?1] ，其中 d[0] = nums[0] ，如下圖所示，
我們可以看到原陣列就是差分陣列的前綴和，
nums[0] = d[0]
num[3] = d[0] + d[1] + d[2] + d[3]
有了差分陣列，如果對區間 [a,b] 每個元素加 3 ，不需要在一個個操作，只需要在兩端修改即可，如下圖所示，
d[a] += 3;
d[b+1] -= 3;
來看下代碼：
public class DiffNums {
private int[] diff;// 差分陣列，
private int[] nums;// 原陣列，
public DiffNums(int[] nums) {
this.nums = nums;
diff = new int[nums.length];
diff[0] = nums[0];
for (int i = 1; i < diff.length; i++)
diff[i] = nums[i] - nums[i - 1];
}
// 給區間[a,b]每個元素增加val（也可為負數），
public void increment(int a, int b, int val) {
diff[a] += val;
if (b + 1 < diff.length)
diff[b + 1] -= val;
}
// 回傳結果陣列，
public int[] result() {
nums[0] = diff[0];
for (int i = 1; i < diff.length; i++)
nums[i] = diff[i] + nums[i - 1];
return nums;
}
}
二維差分陣列
我們把一維差分陣列看做是一條直線，只需要用后面的值減去前面的值就可以構造差分陣列，而二維差分數可以把他看做是一個平面，如下圖所示，他的定義如下：
d[i][j] = a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
如果想獲取原陣列，根據上面的公式可以得到：
a[i][j] = a[i-1][j]+a[i][j-1]-a[i-1][j-1]+d[i][j]
如下圖所示，以 (x1,y1) 為左上角， (x2,y2) 為右下角構成一個區間，如果對這個區間內的每個元素增加 val ，只需要執行下面四步即可，
public void add(int x1, int y1, int x2, int y2, int val) {
d[x1][y1] += val;// 增加S1
d[x1][y2 + 1] -= val;// 減去S2
d[x2 + 1][y1] -= val;// 減去S3
d[x2 + 1][y2 + 1] += val;//加上S4
}
代碼如下：
private int[][] d;// 差分陣列，
private int[][] a;// 原陣列，
public TwoDiffNums(int[][] a) {
this.a = a;
int m = a.length;
int n = a[0].length;
d = new int[m][n];
// 求差分陣列，
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
add(i, j, i, j, a[i][j]);
}
public void add(int x1, int y1, int x2, int y2, int val) {
d[x1][y1] += val;
if (y2 + 1 < d[0].length)
d[x1][y2 + 1] -= val;
if (x2 + 1 < d.length)
d[x2 + 1][y1] -= val;
if (x2 + 1 < d.length && y2 + 1 < d[0].length)
d[x2 + 1][y2 + 1] += val;
}
// 回傳結果陣列，
public int[][] result() {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
int x1 = i > 0 ? a[i - 1][j] : 0;
int x2 = j > 0 ? a[i][j - 1] : 0;
int x3 = i > 0 && j > 0 ? a[i - 1][j - 1] : 0;
a[i][j] = x1 + x2 - x3 + d[i][j];
}
}
return a;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/554776.html
標籤：其他
上一篇：[AGC055B] ABC Supremacy 題解
下一篇：返回列表