This page looks best with JavaScript enabled

Hackerrank - Array Manipulation

方法證明

先將 k 用未知數代替

a b k
1 2 p
2 5 q
3 4 r

普通作法

index: 0 1 2 3 4 5
p p
q q q q
r r
sum: p p+q q+r q+r q

進階作法

  • 因 a 到 b 中間為連續,所以範圍內相減會抵消

    利用此點發展出新方法,得到 sum 後,將 變化量 算出
    Δ[i] = sum[i] - sum[i-1]

index: 0 1 2 3 4 5
sum: p p+q q+r q+r q
Δ: p q r-p 0 -r -q
  • 反過來說,將 Δ 從頭累加會得到該 index 的 sum

  • 拆解成 Δ 後可輕易看出:可以只處理 a 及 b+1 ,

    中間的 (a+1)~(b)不用管,最後再累加即可

整理此進階作法

index: 0 1 2 3 4 5
p: p -p
q: q -q
r: r -r
加總得到上述的 Δ: 0 p q r-p 0 -r -q
累加得到上述的 sum: p p+q q+r q+r q 0

Δ[a] += k

Δ[b+1] -= k

sum[i] = sum[i-1] + Δ[i]


比較

每筆資料的處理次數

次數 b-a+1 2

此方式可使每筆資料處理次數由 b-a+1 降低至 2
而最後的取 max. 增加一個累加的動作,處理次數多 n 次

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def arrayManipulation(n, queries):
    re, s = 0, 0 ## max & sum
    d = [0] * (n+2) ## Δ[]
    for a, b, k in queries:
        d[a] += k
        d[b+1] -= k
    for i in range(1, n+1):
        s += d[i]
        re = max(re, s)
    return re