LeetCode 解題筆記：2161. Partition Array According to Given Pivot

作者：王一哲
日期：2026年6月8日


LeetCode 題目連結：2161. Partition Array According to Given Pivot

解題想法

中等難度題目。題目給一個串列 $nums$ 及樞紐值 $pivot$，要將 $nums$ 的值重新排列，小於 $pivot$ 的值按照原來的順序放在 $pivot$ 的左側，大於 $pivot$ 的值按照原來的順序放在 $pivot$ 的右側，中間是 $pivot$。$pivot$ 一定等於 $nums$ 其中一個或多個數字。我的想法是開兩個串列，其中 $ans$ 用來儲存答案，$large$ 用來儲存大於 $pivot$ 的值在 $nums$ 之中的索引值，另外用一個變數 $cnt$ 記錄 $pivot$ 於 $nums$ 之中的數量。接下來用一個 for 迴圈掃過 $nums$ 取出數值 $num$，如果 $num$ 等於 $pivot$ 就將 $cnt$ 加 1；如果 $num$ 小於 $pivot$ 就將 $num$ 加到 $ans$ 最後面；如果 $num$ 大於 $pivot$ 就將索引值 $i$ 加到 large。將 $cnt$ 個 $pivot$ 接到 $ans$ 之後。最後用一個 for 迴圈，取出 $large$ 記錄的索引值 $i$，將 $nums[i]$ 加到 $ans$ 最後面。程式碼再微調一下應該會更快。

Python 程式碼

Runtime: 40 ms, beats 33.75%. Memory: 34.31 MB, beats 5.07%.

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        ans, large = [], []  # 答案，大於 pivot 的索引值
        cnt = 0  # 等於 pivot 的數字數量
        for i, num in enumerate(nums):  # 依序讀取 nums 的索引值及數字
            if num == pivot:  # num 等於 pivot
                cnt += 1  # 數量加 1
            elif num < pivot:  # num 小於 pivot
                ans.append(num)  # num 加入 ans
            else:  # nums 大於 pviot
                large.append(i)  # 記錄索引值 i
        
        # ans 加上 cnt 個 pivot
        ans += [pivot] * cnt
        # 將 large 對應的數字接到 ans 後面
        for i in large:
            ans.append(nums[i])
        # 回傳答案
        return ans

用索引值找到填入數值的位置，速度反而比較慢。Runtime: 58 ms, beats 18.36%. Memory: 34.23 MB, beats 5.83%.

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        n, le = len(nums), 0  # 長度，從左側填數字的索引值
        ans, large = [0]*n, []  # 答案，大於 pivot 的索引值
        cnt = 0  # 等於 pivot 的數字數量
        for i, num in enumerate(nums):  # 依序讀取 nums 的索引值及數字
            if num == pivot:  # num 等於 pivot
                cnt += 1  # 數量加 1
            elif num < pivot:  # num 小於 pivot
                ans[le] = num  # num 填入 ans[le]
                le += 1  # 向右移 1 格
            else:  # nums 大於 pviot
                large.append(i)  # 記錄索引值 i
        
        # ans[le] ~ ans[le + cnt] 填入 pivot
        ans[le : le+cnt] = [pivot] * cnt
        le += cnt  # 向右移 cnt 格
        # 將 large 對應的數字接到 ans 後面
        for i in large:
            ans[le] = nums[i]
            le += 1
        # 回傳答案
        return ans

C++ 程式碼

Runtime: 16 ms, beats 8.61%. Memory: 137.1 MB, beats 36.22%.

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        vector<int> ans, large;  // 答案，大於 pivot 的索引值
        int n = (int)nums.size(), cnt = 0;  // nums 長度，等於 pivot 的數字數量
        for(int i=0; i<n; i++) {  // 依序讀取 nums 的索引值及數字
            int num = nums[i];
            if (num == pivot) {  // num 等於 pivot
                cnt++;  // 數量加 1
            } else if (num < pivot) {  // num 小於 pivot
                ans.push_back(num);  // num 加入 ans
            } else {  // nums 大於 pviot
                large.push_back(i);  // 記錄索引值 i
            }
        }
        
        // ans 加上 cnt 個 pivot
        for(int i=0; i<cnt; i++) ans.push_back(pivot);
        // 將 large 對應的數字接到 ans 後面
        for(auto idx : large) ans.push_back(nums[idx]);
        // 回傳答案
        return ans;
    }
};

用索引值找到填入數值的位置，速度快很多。Runtime: 8 ms, beats 51.49%. Memory: 131.29 MB, beats 70.35%.

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        int le = 0, n = (int)nums.size(), cnt = 0;  // 於 ans 填入數字的索引值, nums 長度，等於 pivot 的數字數量
        vector<int> ans (n, 0), large;  // 答案，大於 pivot 的索引值
        for(int i=0; i<n; i++) {  // 依序讀取 nums 的索引值及數字
            int num = nums[i];
            if (num == pivot) {  // num 等於 pivot
                cnt++;  // 數量加 1
            } else if (num < pivot) {  // num 小於 pivot
                ans[le] = num;  // num 填入 ans[le]
                le++;
            } else {  // nums 大於 pviot
                large.push_back(i);  // 記錄索引值 i
            }
        }
        
        // ans[le] ~ ans[le + cnt] 填入 pivot
        fill(ans.begin() + le, ans.begin() + le + cnt, pivot);
        le += cnt;
        // 將 large 對應的數字接到 ans 後面
        for(auto idx : large) {
            ans[le] = nums[idx];
            le++;
        }
        // 回傳答案
        return ans;
    }
};