題目資訊

• 題目編號: 2161
• 題目連結: Partition Array According to Given Pivot
• 主題: Array, Two Pointers, Simulation

題目敘述

你有一個0-索引的整數數組 nums 和一個整數 pivot。重新排列 nums 以滿足以下條件：

• 每個小於 pivot 的元素出現在每個大於 pivot 的元素之前。
• 每個等於 pivot 的元素出現在小於和大於 pivot 的元素之間。
• 小於 pivot 的元素和大於 pivot 的元素的相對順序保持不變。
  • 更正式地考慮每個 $p_i$，$p_j$，其中 $p_i$ 是第 $i$ 个元素的新位置而 $p_j$ 是第 $j$ 个元素的新位置。如果 $i < j$ 且兩個元素都小於（或大於）pivot，則有 $p_i < p_j$。

返回 重新排列後的 nums。

範例 1:

輸入: nums = [9,12,5,10,14,3,10], pivot = 10
輸出: [9,5,3,10,10,12,14]
解釋: 
數字 9, 5 和 3 小於樞紐點，所以它們在數組的左側。
數字 12 和 14 大於樞紐點，所以它們在數組的右側。
小於和大於樞紐點的元素的相對順序也保持不變。[9, 5, 3] 和 [12, 14] 是各自的順序。

範例 2:

輸入: nums = [-3,4,3,2], pivot = 2
輸出: [-3,2,4,3]
解釋: 
數字 -3 小於樞紐點，所以它在數組的左側。
數字 4 和 3 大於樞紐點，所以它們在數組的右側。
小於和大於樞紐點的元素的相對順序也保持不變。[-3] 和 [4, 3] 是各自的順序。

約束條件:

• $1 \leq \text{nums.length} \leq 10^5$
• $-10^6 \leq \text{nums}[i] \leq 10^6$
• pivot 等於 nums 中的一個元素。

直覺

這個問題的本質在於根據給定的 pivot 重新排列一個數組。核心思想是將數組分為三個不同的部分：小於 pivot 的元素、等於 pivot 的元素和大於 pivot 的元素。通過維持這些部分，並且不改變其中元素的相對順序，我們可以確保數組符合給定的要求，並且保持相對於 pivot 的穩定性。

解法

此解法使用輔助數據結構來有效地分類和重新排列元素：

1. 初始化：

   • 使用兩個隊列：less 用於存儲小於 pivot 的元素，greater 用於存儲大於 pivot 的元素。隊列在這裡非常合適，因為它們保留了元素的順序，這對於維持相對順序至關重要。

2. 分類：

   • 遍歷給定的 nums 數組。對於 nums 中的每一個元素，將其與 pivot 進行比較。
     • 如果元素小於 pivot，將其添加到 less 隊列。
     • 如果元素大於 pivot，將其添加到 greater 隊列。
     • 等於 pivot 的元素不會被添加到任何隊列中，因為稍後會在原地處理這些元素。

3. 重構：

   • 初始化一個索引 idx 為 0，用於覆蓋 nums 數組。
   • 將 less 隊列中的所有元素出列，並從開始位置覆蓋 nums，同時將 idx 向前移動。
   • 接下來，用 pivot 本身填充從當前 idx 位置開始的數組位置。需要放置的 pivot 元素數量由數組的總大小減去 less 和 greater 隊列的總大小決定。
   • 最後，將所有 greater 隊列中的元素出列，從更新後的 idx 開始繼續覆蓋 nums。

這種方法確保小於或大於 pivot 的元素之間的原始順序得到保持，同時有效地將元素圍繞 pivot 進行分區。該方法的時間複雜度為 $O(n)$，其中 $n$ 為 nums 中的元素數量，因為每個元素僅處理一次，且與隊列相關的操作為常數時間。

程式碼

C++

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        // 用於存儲小於和大於 pivot 的元素的隊列
        queue<int> less, greater;

        // 根據元素與 pivot 的關係分類
        for (int num : nums) {
            if (num < pivot) {
                less.push(num);
            } else if (num > pivot) {
                greater.push(num);
            }
        }

        int idx = 0;

        // 將小於 pivot 的元素放到 nums 的開頭
        while (!less.empty()) {
            nums[idx++] = less.front();
            less.pop();
        }

        // 將等於 pivot 的元素放到 nums 的中間
        for (; idx < nums.size() - greater.size(); idx++) {
            nums[idx] = pivot;
        }

        // 將大於 pivot 的元素放到 nums 的末尾
        while (!greater.empty()) {
            nums[idx++] = greater.front();
            greater.pop();
        }

        return nums;
    }
};

Python

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        # 儲存小於和大於樞紐值的元素的佇列
        less = deque()
        greater = deque()

        # 根據元素與樞紐值的關係進行分類
        for num in nums:
            if num < pivot:
                less.append(num)
            elif num > pivot:
                greater.append(num)

        idx = 0

        # 將小於樞紐值的元素放在nums的起始位置
        while less:
            nums[idx] = less.popleft()
            idx += 1

        # 將等於樞紐值的元素放在nums的中間
        for _ in range(idx, len(nums) - len(greater)):
            nums[idx] = pivot
            idx += 1

        # 將大於樞紐值的元素放在nums的末尾
        while greater:
            nums[idx] = greater.popleft()
            idx += 1

        return nums

複雜度分析

• 時間複雜度: $O(n)$，其中 $n$ 是輸入陣列 nums 的長度。這是因為演算法遍歷 nums 陣列一次，以將元素分類到 “less” 和 “greater” 隊列，然後遍歷這些隊列以重新安排 nums 中的元素。每個操作（推入或彈出隊列，以及寫回至 nums）皆需常數時間 $O(1)$，因此整體的時間複雜度為線性。

• 空間複雜度: $O(n)$，其中 $n$ 是輸入陣列 nums 的長度。這是因為我們需額外的空間來儲存 “less” 和 “greater” 隊列中的元素。在最壞的情況下，所有元素皆小於或大於樞紐值時，所需的空間將與輸入陣列 nums 的大小成正比。