題目資訊

• 題目編號: 2529
• 題目連結: Maximum Count of Positive Integer and Negative Integer
• 主題: Array, Binary Search, Counting

題目敘述

給定一個非遞減排序的陣列 nums，返回正整數數量與負整數數量之間的最大值。

• 換句話說，如果 nums 中正整數的數量是 pos，負整數的數量是 neg，則返回 pos 和 neg 中較大的數。

注意 0 既不是正數也不是負數。

範例 1:

輸入: nums = [-2,-1,-1,1,2,3]
輸出: 3
解釋: 這裡有 3 個正整數和 3 個負整數。它們中最大的數量是 3。

範例 2:

輸入: nums = [-3,-2,-1,0,0,1,2]
輸出: 3
解釋: 這裡有 2 個正整數和 3 個負整數。它們中最大的數量是 3。

範例 3:

輸入: nums = [5,20,66,1314]
輸出: 4
解釋: 這裡有 4 個正整數和 0 個負整數。它們中最大的數量是 4。

約束條件:

• $1 \leq \text{nums.length} \leq 2000$
• $-2000 \leq \text{nums}[i] \leq 2000$
• nums 是按非遞減順序排序的。

進一步思考: 你能在 $O(\log(n))$ 的時間複雜度內解決這個問題嗎？

直覺

這個問題要求我們在一個已排序的數組中確定正數和負數之間的最大計數。由於數列是以非減的順序排序，正整數將位於任何負數和零之後。這允許我們有效地使用基於二元搜尋的算法來識別負數和正整數之間的邊界。通過定位第一個正整數和最後一個負整數，我們可以計算它們各自的數量並返回兩者中較大的那一個。

解法

要解決這個問題，我們利用已排序數組的性質並結合二元搜尋技術。主要步驟如下：

1. 計算正整數的數量：使用 upper_bound 找到第一個大於 0 的元素。正整數的數量是從該迭代器到數組末尾的距離。upper_bound 有效地使用二元搜尋方法，以 $O(\log(n))$ 時間找到這個邊界。

2. 計算負整數的數量：使用 lower_bound 定位第一個不小於 0 的元素，從而有效地識別負數和零/正數之間的邊界。負整數的數量可以通過計算從數組開頭到這個邊界的距離來確定。與 upper_bound 相似，lower_bound 也以 $O(\log(n))$ 時間運行。

3. 確定最大計數：在獲得兩個計數後，只需通過使用 max 函數返回正整數和負整數數量之間的最大值。

由於數組是已排序的，這些步驟利用對數搜尋技術確保了解決方案的高效性，從而符合問題的約束和複雜度。

程式碼

C++

class Solution {
public:
    int maximumCount(vector<int>& nums) {
        // 計算正整數的數量。
        // upper_bound 返回指向第一個大於 0 的元素的迭代器。
        int positiveCount = nums.end() - upper_bound(nums.begin(), nums.end(), 0);

        // 計算負整數的數量。
        // lower_bound 返回指向第一個不小於 0 的元素的迭代器。
        int negativeCount = lower_bound(nums.begin(), nums.end(), 0) - nums.begin();

        // 返回正整數和負整數中較大的一方的數量。
        return max(positiveCount, negativeCount);
    }
};

Python

class Solution:
    def maximumCount(self, nums):
        # 計算正整數的數量。
        # bisect_right 回傳第一個大於 0 的元素的索引。
        positiveCount = len(nums) - bisect.bisect_right(nums, 0)

        # 計算負整數的數量。
        # bisect_left 回傳第一個不小於 0 的元素的索引。
        negativeCount = bisect.bisect_left(nums, 0)

        # 回傳正整數和負整數中較大的數量。
        return max(positiveCount, negativeCount)

複雜度分析

• 時間複雜度: $O(\log n)$。此時間複雜度來自於使用 upper_bound 和 lower_bound 函數。這兩個函數利用二分搜尋，因為它們是 C++ 標準庫中針對已排序範圍的演算法的一部分，因此運行於 $O(\log n)$ 的時間複雜度。

• 空間複雜度: $O(1)$。該演算法使用固定數量的額外空間來存儲如 positiveCount 和 negativeCount 的整數變數。因此，無額外空間需求會隨輸入 nums 的大小擴展。