題目描述:
一個整數的「陣列形式」是由其每一位數字組成的陣列。例如 1234 的陣列形式為 [1, 2, 3, 4]。給定一個非負整數的陣列形式 num 和一個整數 k,返回 num + k 的陣列形式。
解題思路: 逐位相加法:
將 k 視為「進位」,從 num 的最低位開始,每一位加上 k 的當前最低位:
num 的末尾開始向前遍歷。sum = num[i] + k % 10,k /= 10。sum >= 10),加到 k 上:k += sum / 10,num[i] = sum % 10。num 後,若 k > 0,繼續在前面插入 k 的各位數字。時間複雜度:O(max(n, log k)) — 其中 n 是 num 的長度,log k 是 k 的位數。最差情況下需要處理兩者中較長的。
空間複雜度:O(1) — 原地修改 num(不計結果本身)。insert(begin) 操作每次 O(n),總計最差 O(n * log k);如果改用反轉則可避免。
1. Set i = len(num) - 1. 2. While i >= 0 or k > 0: a. If i >= 0: k += num[i]. b. Set current digit = k % 10. c. k = k / 10. d. If i >= 0: num[i] = current digit, decrement i. e. Else: prepend current digit to num. 3. Return num.
反轉 + 尾部追加:O(max(n, log k)) 時間、O(1) 額外空間。先反轉 num,逐位相加並在尾部追加(O(1) amortized),最後再反轉回來。避免了 insert(begin) 的 O(n) 開銷。
使用 deque:O(max(n, log k)) 時間、O(n) 空間。用雙端佇列存放結果,在前端插入為 O(1)。
insert(begin) 操作的時間複雜度為什麼是 O(n)?如何用反轉技巧來避免?k 可能是負數(即做減法),演算法需要如何修改?