LeetCode 解題筆記：2948. Make Lexicographically Smallest Array by Swapping Elements

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


LeetCode 題目連結：2948. Make Lexicographically Smallest Array by Swapping Elements

解題想法

中等難度題。題目給一個陣列 $nums$ 及整數 $limit$，每次操作時可以選擇陣列中的兩個整數 $nums[i], nums[j]$，如果 $| nums[i] - nums[j] | \leq limit$ 可以將兩者的位置交換，操作次數不限，回傳可得的最小字典序陣列。這題我是將 $nums$ 之中的數值及索引值組成 tuple 或 pair 存入另一個陣列 $data$ 之中，將 $data$ 依照數值由小到大排序；依序由排序後的 $data$ 讀取資料，將數值及索引值分組分別存入陣列 $values$ 及 $indices$；再從 $values$ 及 $indices$ 讀取分組後的數值，將同組的索引值排序之後，依照索引值將數值填入 $nums$ 之中。

Python 程式碼

Runtime: 259 ms, beats 68.66%. Memory: 54.76 MB, beats 43.28%.

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        # 將 nums 之中的值組成 (num, idx) 放入 data 之中再排序
        data = sorted((num, idx) for idx, num in enumerate(nums))
        # 相差 k 以內的數字放同一組，數字、索引值分開放
        values = [[data[0][0]]]
        indices = [[data[0][1]]]
        for val, idx in data[1:]:
            if val - values[-1][-1] <= limit:  # 可以放在最後一組
                values[-1].append(val)
                indices[-1].append(idx)
            else:  # 新的一組
                values.append([val])
                indices.append([idx])
        # indices 每組排序後，依照 idx 將 values 的值填入 nums 再回傳
        for vals, idxs in zip(values, indices):
            idxs.sort()
            for val, idx in zip(vals, idxs):
                nums[idx] = val
        return nums

C++ 程式碼

Runtime: 251 ms, beats 53.80%. Memory: 205.47 MB, beats 43.66%.

class Solution {
public:
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
        int n = (int)nums.size();  // 數量
        /* 將 nums 之中的值組成 (num, idx) 放入 data 之中再排序 */
        vector<pair<int, int>> data (n);
        for(int i = 0; i < n; i++) {
            data[i] = {nums[i], i};
        }
        sort(data.begin(), data.end());
        /* 相差 k 以內的數字放同一組，數字、索引值分開放 */
        vector<vector<int>> values = {{data[0].first}};
        vector<vector<int>> indices = {{data[0].second}};
        for(int i = 1; i < n; i++) {
            int val = data[i].first, idx = data[i].second;
            if (val - values.back().back() <= limit) {  // 可以放在最後一組
                values.back().push_back(val);
                indices.back().push_back(idx);
            } else {  // 新的一組
                values.push_back({val});
                indices.push_back({idx});
            }
        }
        /* indices 每組排序後，依照 idx 將 values 的值填入 nums 再回傳 */
        int m = (int)values.size();  // 組數
        for(int i = 0; i < m; i++) {
            vector<int> vals = values[i], idxs = indices[i];
            sort(idxs.begin(), idxs.end());
            int d = (int)vals.size();  // 這組內的資料數量
            for(int j = 0; j < d; j++) {
                nums[idxs[j]] = vals[j];
            }
        }
        return nums;
    }
};