Description
給定整數陣列
nums，令product為所有元素的乘積。回傳product的正負號：若為正回傳 1，若為負回傳 -1，若為 0 回傳 0。
Example:
Input: nums = [-1,-2,-3,-4,3,2,1] Output: 1 （乘積為 144，是正數）
Intuition#
核心思路：不需要計算真正的乘積（會 overflow），只需追蹤符號。遇到 0 直接回傳 0，否則計算負數的個數——偶數個負數為正，奇數個為負。
- 任何元素為 0 -> 乘積為 0
- 否則只看負數的個數：偶數 -> 正，奇數 -> 負
Approaches#
1: Count Negatives#
- 概念: 遍歷一次，遇到 0 直接回傳，否則計算負數個數
- 時間複雜度:
O(n)- 一次遍歷 - 空間複雜度:
O(1)- 只用一個計數器
class Solution {
fun arraySign(nums: IntArray): Int {
var negCount = 0
for (num in nums) {
if (num == 0) return 0
if (num < 0) negCount++
}
return if (negCount % 2 == 0) 1 else -1
}
}⭐2: Sign Tracking#
- 概念: 維護一個
sign變數，遇到負數就翻轉符號，遇到 0 直接回傳 - 時間複雜度:
O(n)- 一次遍歷 - 空間複雜度:
O(1)- 只用常數變數
class Solution {
fun arraySign(nums: IntArray): Int {
var sign = 1
for (num in nums) {
if (num == 0) return 0
if (num < 0) sign = -sign
}
return sign
}
}這題的重點是避免實際計算乘積，因為乘積可能超出 Long 的範圍。只追蹤符號是正確且高效的做法。
🔑 Takeaways#
- Pattern: 乘積符號問題 -> 只追蹤符號，不計算實際值
- 關鍵技巧: 翻轉符號的技巧
sign = -sign比計數負數更簡潔。遇到 0 提前回傳是常見的剪枝