LeetCode: 1822-Sign of the Product of an Array 解題紀錄

題目

There is a function signFunc(x) that returns:

• 1 if x is positive.
• -1 if x is negative.
• 0 if x is equal to 0.

You are given an integer array nums. Let product be the product of all values in the array nums.

Return signFunc(product).

Example 1:

Input: nums = [-1,-2,-3,-4,3,2,1]
Output: 1
Explanation: The product of all values in the array is 144, and signFunc(144) = 1

Example 2:

Input: nums = [1,5,0,2,-3]
Output: 0
Explanation: The product of all values in the array is 0, and signFunc(0) = 0

Example 3:

Input: nums = [-1,1,-1,1,-1]
Output: -1
Explanation: The product of all values in the array is -1, and signFunc(-1) = -1

Constraints:

• 1 <= nums.length <= 1000
• -100 <= nums[i] <= 100

我們會獲得一個純數值的陣列，並且要根據所有數值乘積的正負來回傳 1 或 -1。如果等於 0 的情況則直接回傳 0。

---

解題思路

由於直接把所有矩陣中的元素相乘會很容易超出 INT 的上限，所以實際上我們只需要計算陣列中的負數出現次數即可判斷最後乘積的正負；順帶一提，如果陣列中出現 0，則意味著最後的乘積一定是 0。

複雜度

Time Complexity	O(n)
Space Complexity	O(1)

C++ 範例程式碼

class Solution {
public:
    int arraySign(vector<int>& nums) {
        // Init
        int neg = 0;

        // Count the `neg` number
        for (int& num: nums) {
            if (num < 0) {
                ++neg;
            }
            else if (num == 0) {
                return 0;
            }
        }

        // If `neg` is odd, return -1; else return 1 
        return neg % 2 ? -1 : 1;
    }
};

Python 範例程式碼

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        # Init
        neg = 0

        # Count the `neg` number
        for num in nums:
            if num < 0:
                neg += 1
            elif num == 0:
                return 0

        # If `neg` is odd, return -1; else return 1 
        return -1 if neg % 2 else 1

---

References

• 1822. Sign of the Product of an Array

---

Read More

• LeetCode 解題紀錄目錄