🔗 🟡 3011. Find if Array Can Be Sorted 1497

tags: `Biweekly Contest 122` `陣列(Array)` `模擬(Simulation)`

題意

給定一個下標從 $0$ 開始的正整數陣列 $nums$ 。

在一個操作中，如果兩個相鄰元素在二進位下 $1$ 的個數相同，那麼可以將這兩個元素交換。可以執行這個操作 任意次（包含 $0$ 次）。

如果可以排序陣列，返回 $True$ ，否則返回 $False$ 。

約束條件

$1 \leq \text{nums.length} \leq 100$
$1 \leq \text{nums[i]} \leq 2^8$

思路：分組循環 + 維護組內最大值

根據題意，只有相鄰且二進位下 $1$ 的個數相同的元素可以交換，而若相鄰的某些元素都能交換，則在若干次操作後這些元素都可以互相交換。因此我們可以將陣列中的元素根據它們的二進位表示中 $1$ 的個數進行分組，對於每一組組內元素，我們可以任意交換相鄰的兩個元素。

在若干次交換後必定可以使得組內元素是有序的，因此我們只需要考慮不同組之間的元素是否是有序的。為此我們需要檢查當前組內的最小值是否大於上一組的最大值，如果是則無法通過交換操作將整個陣列排序。

具體步驟如下：

使用一個指標 $i$ 從左向右遍歷陣列，並初始化變數 $pre\_mx$ 為 $-1$ ，用於記錄前一組的最大值。這裡使用 $-1$ 是因為陣列中的元素均為正整數。
對於當前指標 $i$ 所指向的元素 $nums[i]$ ，計算它二進位下 $1$ 的個數 $cnt$ 。
從 $i$ 開始，不斷向右移動指標，直到遇到一個二進位下 $1$ 的個數不等於 $cnt$ 的元素為止。這樣可以遍歷完當前元素所在的組。
在遍歷該組的過程中，維護該組內的最大值 $mx$ 。同時檢查當前元素是否小於上一組的最大值 $pre\_mx$ ，如果小於則說明無法通過交換操作將整個陣列排序，直接返回 $False$ 。
遍歷完當前組後，更新 $pre\_mx$ 為當前組的最大值 $mx$ ，然後繼續遍歷下一組。
如果能夠遍歷完整個陣列且沒有返回 $False$ ，則說明可以通過交換操作將整個陣列排序，返回 $True$ 。

複雜度分析

時間複雜度： $O(n)$ ，其中 $n$ 是陣列的長度。
空間複雜度： $O(1)$ 。

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        n = len(nums)
        i = 0
        pre_mx = -1
        while i < n:
            mx = nums[i]
            cnt = nums[i].bit_count()
            while i < n and nums[i].bit_count() == cnt:
                if nums[i] < pre_mx:
                    return False
                mx = max(mx, nums[i])
                i += 1
            pre_mx = mx
        return True

class Solution {
public:
    bool canSortArray(vector<int>& nums) {
        int n = nums.size(), i = 0, pre_mx = -1;
        while (i < n) {
            int mx = nums[i];
            int cnt = __builtin_popcount(nums[i]);
            while (i < n && __builtin_popcount(nums[i]) == cnt) {
                if (nums[i] < pre_mx) return false;
                mx = max(mx, nums[i]);
                i++;
            }
            pre_mx = mx;
        }
        return true;
    }
};