2161. Partition Array According to Given Pivot

題目 / Problem

中文： 給定一個 0-indexed（從 0 開始編號）的整數陣列 nums 和一個整數 pivot（樞紐值）。請重新排列 nums，使其滿足以下條件：

1. 所有 小於 pivot 的元素，都排在所有 大於 pivot 的元素 之前。
2. 所有 等於 pivot 的元素，都排在「小於」與「大於」兩組之間。
3. 小於 pivot 的那些元素之間，要保持原本的相對順序；大於 pivot 的那些元素之間也一樣要保持原本的相對順序。

回傳重排後的 nums。

English: You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums so that:

1. Every element less than pivot comes before every element greater than pivot.
2. Every element equal to pivot sits in between the smaller and larger groups.
3. The relative order of the "less than" elements must be preserved, and likewise the relative order of the "greater than" elements.

Return the rearranged nums.

Constraints / 限制： - 1 <= nums.length <= 10^5 - -10^6 <= nums[i] <= 10^6 - pivot 必定等於 nums 中的某個元素 / pivot equals at least one element of nums.

Worked example / 範例：

Input:  nums = [9,12,5,10,14,3,10], pivot = 10
Output: [9,5,3,10,10,12,14]

• 小於 10 的：9, 5, 3（按原順序）/ Less than 10: 9, 5, 3 (original order)
• 等於 10 的：10, 10 / Equal to 10: 10, 10
• 大於 10 的：12, 14（按原順序）/ Greater than 10: 12, 14 (original order)

名詞解釋 / Glossary

• 陣列 / Array：一段連續的記憶體，存放相同型別的元素，用索引（index）0, 1, 2… 來存取。/ A contiguous block of memory holding same-typed elements, accessed by index 0, 1, 2…
• 樞紐值 / Pivot：本題用來把元素分成「比它小／等於它／比它大」三組的基準數字。/ The reference value we use to split elements into three groups: smaller, equal, larger.
• 相對順序 / Relative order：兩個元素在輸出中的前後關係，要和它們在輸入中的前後關係一致。/ The before/after relationship between two elements must match their order in the input.
• 穩定 / Stable：一種「不會打亂相同類別元素原本順序」的處理方式。本題要求對「小於組」和「大於組」保持穩定。/ A property meaning elements that fall in the same category keep their original ordering. Required here for the smaller and larger groups.
• 雙指針 / Two pointers：用兩個（或更多）索引變數同時掃描或填寫陣列的技巧，常用來省去額外空間。/ A technique using two (or more) index variables to scan or fill an array, often to avoid extra memory.
• 三趟掃描 / Three passes：把陣列從頭到尾走完，重複三次（先放小於、再放等於、最後放大於），每趟做一件事。/ Walking the array start-to-end three separate times, each pass doing one job.
• malloc / 動態配置記憶體：C 語言中在執行期向系統要一塊記憶體的函式，回傳指標；用完要 free（但 LeetCode 會自行管理回傳陣列）。/ A C function that requests a block of memory at runtime and returns a pointer.
• vector：C++ 標準函式庫的動態陣列，會自動管理大小，可用 push_back 在尾端加元素。/ C++ standard-library dynamic array that grows automatically; push_back appends to the end.

思路

中文：最直覺的暴力想法是「排序」。如果我們對整個陣列排序，小的自然在前、大的在後，看起來符合要求。但問題是排序會打亂相同大小元素的原始順序，而且更嚴重的是——本題要求「小於組」和「大於組」各自保持輸入時的相對順序，普通排序（即使穩定排序）會把不同數值重新排列，因此並不符合要求。舉例 [9,5,3] 必須維持成 9、5、3，而不是排序後的 3、5、9。所以排序這條路行不通，我們需要更貼合題意的做法。

關鍵觀察是：每個元素其實只屬於三類之一——小於 pivot、等於 pivot、大於 pivot。而輸出就是這三類「按順序接起來」：先全部小於的、再全部等於的、最後全部大於的。對於小於組和大於組，我們只要「照著原陣列從左到右遇到誰就放誰」，自然就保持了相對順序。等於組則只需要知道有幾個，因為它們都一樣（都是 pivot），順序無所謂。於是演算法是：開一個新陣列，做三趟掃描。第一趟把所有「小於 pivot」的元素依序寫進去；第二趟把所有「等於 pivot」的元素（其實就是補上對應數量的 pivot）寫進去；第三趟把所有「大於 pivot」的元素依序寫進去。我們用一個寫入位置指標 k，每寫一個就往後移一格，這就是雙指針／填寫指標的概念。三趟都是線性掃描，總時間 O(n)，而且天然保持了所需的相對順序。

English: The most naive idea is to sort the array — small values drift to the front, large to the back. But sorting breaks what the problem demands: it reorders distinct values, whereas we must keep the original left-to-right order within the "less than" group and within the "greater than" group. For instance [9,5,3] must stay as 9, 5, 3, not become the sorted 3, 5, 9. So sorting is the wrong tool.

The key insight is that every element belongs to exactly one of three buckets — less than, equal to, or greater than the pivot — and the answer is simply those three buckets concatenated in that order. For the "less" and "greater" buckets, if we just copy elements in the same left-to-right order we encounter them, relative order is preserved for free. The "equal" bucket is trivial: every such element is identical (it equals the pivot), so we only need to know how many there are. This gives a clean three-pass algorithm into a fresh output array, using a single write index k that advances each time we place a value (a "fill pointer"). Pass 1 copies every element < pivot; pass 2 writes the pivot the right number of times for the == pivot elements; pass 3 copies every element > pivot. Three linear scans → O(n) time, with the required relative order maintained automatically.

逐步走查 / Walkthrough

用範例 nums = [9,12,5,10,14,3,10], pivot = 10。建立輸出 res，寫入指標 k 從 0 開始。/ Using the sample. We build res with write index k starting at 0.

Pass 1 — 收集「小於 10」/ collect elements < 10 (從左到右掃 / scan left-to-right):

Pass 2 — 收集「等於 10」/ collect elements == 10:

Pass 3 — 收集「大於 10」/ collect elements > 10:

最終 res = [9,5,3,10,10,12,14]，與預期輸出一致。/ Final res = [9,5,3,10,10,12,14], matching the expected output.

Solution — C

// 演算法 / Algorithm:
// 三趟線性掃描 / three linear passes. Pass 1 copies all elements < pivot in order,
// pass 2 copies all elements == pivot, pass 3 copies all elements > pivot.
// 各組天然保持原相對順序 / each group keeps its original relative order automatically.

/**
 * LeetCode 的簽名：回傳新陣列，並透過 returnSize 回傳長度。
 * LeetCode signature: return a new array and report its length via returnSize.
 */
int* pivotArray(int* nums, int numsSize, int pivot, int* returnSize) {
    // 配置一塊和輸入一樣大的記憶體當作答案陣列。
    // Allocate an answer array the same size as the input.
    // malloc 回傳指向該記憶體的指標 / malloc returns a pointer to that memory.
    int* res = (int*)malloc(sizeof(int) * numsSize);

    // k 是「下一個要寫入的位置」/ k is the next write slot in res.
    int k = 0;

    // 第一趟：把所有小於 pivot 的元素，依原順序填入。
    // Pass 1: copy every element strictly less than pivot, in order.
    for (int i = 0; i < numsSize; i++) {       // i 從頭掃到尾 / scan i from start to end
        if (nums[i] < pivot) {                 // 只挑「小於」的 / pick only the smaller ones
            res[k] = nums[i];                  // 寫入答案 / write into res at slot k
            k++;                               // 寫入位置前移一格 / advance the write slot
        }
    }

    // 第二趟：把所有等於 pivot 的元素填入。
    // Pass 2: copy every element equal to pivot.
    // 它們都等於 pivot，順序無所謂 / they are all equal to pivot, so order does not matter.
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == pivot) {                // 只挑「等於」的 / pick only the equal ones
            res[k] = nums[i];                  // 寫入（其值就是 pivot）/ write it (equals pivot)
            k++;                               // 前移寫入位置 / advance write slot
        }
    }

    // 第三趟：把所有大於 pivot 的元素，依原順序填入。
    // Pass 3: copy every element strictly greater than pivot, in order.
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > pivot) {                 // 只挑「大於」的 / pick only the larger ones
            res[k] = nums[i];                  // 寫入答案 / write into res
            k++;                               // 前移寫入位置 / advance write slot
        }
    }

    // 告訴呼叫者答案陣列的長度（和輸入一樣長）。
    // Tell the caller the length of the answer array (same as input).
    *returnSize = numsSize;                    // *returnSize 是解參考並賦值 / dereference and assign

    return res;                                // 回傳答案陣列的指標 / return the pointer to res
}

Solution — C++

// 演算法 / Algorithm:
// 三趟線性掃描 / three linear passes into a result vector. Pass 1 collects elements
// < pivot, pass 2 collects == pivot, pass 3 collects > pivot. Relative order within
// the smaller and larger groups is preserved because we scan left-to-right.
class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        // vector<int> 是會自動管理大小的動態陣列 / a dynamic array that manages its own size.
        vector<int> res;
        // 預先保留 nums.size() 空間，避免多次擴容 / reserve capacity to avoid repeated reallocation.
        res.reserve(nums.size());

        // 第一趟：收集所有小於 pivot 的元素。
        // Pass 1: collect every element strictly less than pivot.
        // range-for：x 依序取每個元素的值 / range-for: x takes each element's value in order.
        for (int x : nums) {
            if (x < pivot) {           // 只要小於的 / keep only smaller ones
                res.push_back(x);      // push_back 在尾端加一個元素 / append x to the end
            }
        }

        // 第二趟：收集所有等於 pivot 的元素。
        // Pass 2: collect every element equal to pivot (order among them is irrelevant).
        for (int x : nums) {
            if (x == pivot) {          // 只要等於的 / keep only equal ones
                res.push_back(x);      // 尾端加入（值即為 pivot）/ append it (value is pivot)
            }
        }

        // 第三趟：收集所有大於 pivot 的元素。
        // Pass 3: collect every element strictly greater than pivot.
        for (int x : nums) {
            if (x > pivot) {           // 只要大於的 / keep only larger ones
                res.push_back(x);      // 尾端加入 / append x to the end
            }
        }

        return res;                    // 回傳結果 vector / return the result vector
    }
};

複雜度 / Complexity

• Time: O(n) — 我們對長度為 n 的陣列做了三趟掃描，3n 仍是線性，主導項是元素總數 n（n 指 nums.length）。/ We scan the length-n array three times; 3n is still linear, dominated by the number of elements n (= nums.length).
• Space: O(n) — 額外開了一個和輸入一樣大的答案陣列／vector，需要 n 個整數空間。（若不算必須回傳的輸出陣列，則只用了常數個變數 k、i。）/ We allocate one answer array/vector of size n. (Excluding the required output, only a constant number of helper variables are used.)

Pitfalls & Edge Cases

• 不能用排序 / Don't reach for sort：一般排序會依數值重排，破壞「小於組」「大於組」各自的原始相對順序（題目明確要求保持）。三趟掃描天然保留順序。/ Sorting reorders by value and destroys the required relative ordering within groups; the three-pass scan preserves it.
• 必須是嚴格比較 / Use strict comparisons：第一趟用 <、第三趟用 >，等於 pivot 的要留給第二趟。若誤用 <= 或 >=，等於 pivot 的元素會被重複放入或放錯位置。/ Pass 1 uses <, pass 3 uses >; equal elements belong to pass 2. Using <=/>= would duplicate or misplace the pivot elements.
• 重複的 pivot / Duplicate pivots：可能有多個元素等於 pivot（範例就有兩個 10）。第二趟逐一掃描而不是只放一個，確保數量正確。/ There can be multiple elements equal to the pivot (the sample has two 10s); pass 2 scans each one so the count is correct.
• 負數與大小 / Negatives and range：元素可為負（如範例 2 的 -3），數值落在 ±10^6，遠在 int 範圍內，不會溢位。比較運算對負數同樣正確。/ Elements can be negative and stay within ±10^6, comfortably inside int; no overflow, and comparisons work for negatives.
• 回傳長度 / Return size (C)：在 C 版本別忘了設定 *returnSize = numsSize，否則 LeetCode 讀不到輸出長度，會判錯。/ In C, you must set *returnSize; forgetting it makes the judge read the wrong length.
• 單一元素 / Single element：長度為 1 時（pivot 必為該元素），三趟中只有第二趟寫入，輸出就是原陣列，邏輯依然正確。/ With length 1 (the pivot is that element), only pass 2 writes; output equals input, still correct.