LeetCode 解題筆記：3644. Maximum K to Sort a Permutation

作者：王一哲
日期：2026年10月23日


LeetCode 題目連結：3644. Maximum K to Sort a Permutation

解題想法

中等難度題。題目給一個長度為 $n ~(1 \leq n \leq 10^5)$ 、數字不重複的整數陣列 $nums ~(0 \leq nums[i] \leq n-1)$。如果 $nums[i] ~\text{&}~ nums[j] = k, i \leq j$，可以交換 $nums[i], nums[j]$，交換次數不限。如果可以用這樣的交換方式使 $nums$ 變為由小到大排序，則最大的 $k$ 值為何？

這題考位元運算，困難之處在於如何找到並證明答案。先將答案 $ans$ 設定為所有位元都是 $1$ 的數字，例如 $2^30 - 1$ 或 $-1$。用一個 for 迴圈掃過 $nums$，如果 $nums[i] \neq i$，代表這個數字需要被交換，更新 $ans ~\text{&}= i$，同時設定排序狀態 is_sorted 為 False。檢查完所有的數字之後，如果 is_sorted 為 True 回傳 $0$，反之回傳 $ans$。

因為位元運算 & 的特性，將 $nums$ 之中任意兩個數字取 & 只會越取越小，答案一定小於 $n$。如果將 $ans$ 與所有需要歸位的數字取 & 之後，$ans$ 的值一定等於 $nums$ 之中的某一個數字，先假設這個數字為 $m$。如果要讓另外兩個數字 $a, b$ 歸位，可以先交換 $a, m$，再交換 $b, m$，最後交換 $a, m$，就可以 $a, b$ 的位置互換，$m$ 最後又回到原來的位置。重複以上的過程就能讓所有的數字歸位。

Python 程式碼

Runtime: 31 ms, beats 63.74%. Memory: 31.90 MB, beats 73.63%.

class Solution:
    def sortPermutation(self, nums: List[int]) -> int:
        is_sorted = True  # 是否已排序
        ans = (1 << 30) - 1  # 答案，先預設成所有位元都是 1 的數字
        for i, num in enumerate(nums):  # 掃過每一個數字
            if i != num:  # 不在正確位置的數字
                is_sorted = False
                ans &= i
        return 0 if is_sorted else ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 152.81 MB, beats 21.90%.

class Solution {
public:
    int sortPermutation(vector<int>& nums) {
        bool is_sorted = true;  // 是否已排序
        int ans = (1 << 30) - 1, n = (int)nums.size();  // 答案，先預設成所有位元都是 1 的數字；長度
        for(int i = 0; i < n; i++) {  // 掃過每一個數字
            if (i != nums[i]) {  // 不在正確位置的數字
                is_sorted = false;
                ans &= i;
            }
        }
        return (is_sorted ? 0 : ans);
    }
};

C 語言程式碼

Runtime: 2 ms, beats 14.29%. Memory: 19.69 MB, beats 100.00%.

int sortPermutation(int* nums, int numsSize) {
    int is_sorted = 1;  // 是否已排序
    int ans = (1 << 30) - 1;  // 答案，先預設成所有位元都是 1 的數字
    for(int i = 0; i < numsSize; i++) {  // 掃過每一個數字
        if (i != nums[i]) {  // 不在正確位置的數字
            is_sorted = false;
            ans &= i;
        }
    }
    return (is_sorted ? 0 : ans);
}