解題說明
Sign of the Product of an Array
題目描述:
給定一個整數陣列 nums,定義函式 signFunc(x):x 為正回傳 1,x 為負回傳 -1,x 為零回傳 0。求陣列所有元素乘積的 signFunc 值。
解題思路: 不需要真的計算乘積(可能溢位),只需追蹤乘積的正負號:
- 如果遇到 0,乘積為 0,直接回傳 0。
- 如果遇到負數,正負號翻轉。
- 正數不影響正負號。
遍歷一次陣列,計算負數的個數。若有零則回傳 0,負數個數為偶數回傳 1,奇數回傳 -1。
C++ 解法
複雜度分析
時間複雜度:O(n) — 遍歷陣列一次,每個元素做常數操作。
空間複雜度:O(1) — 只使用一個符號變數。
虛擬碼
1. Initialize sign = 1 2. For each num in nums: a. If num == 0, return 0 b. If num < 0, flip sign (sign = -sign) 3. Return sign
其他解法
計算負數個數 O(n):先檢查是否有零,再統計負數個數,用奇偶性決定符號。邏輯等價但需要兩次判斷。
用 reduce/accumulate O(n):函數式風格,用 accumulate 搭配 lambda 逐步累積符號。寫法簡潔但可讀性因人而異。
延伸思考
- 如果需要回傳實際乘積而非符號,如何處理大數溢位問題?
- 如果陣列會動態更新(插入/刪除元素),如何高效維護乘積的符號?
- 能否在不使用乘法的情況下判斷乘積的符號(例如只用位元運算)?