解題說明
GCD Sort of an Array
題目描述:給定一個整數陣列 nums,可以任意次交換兩個元素 nums[i] 和 nums[j],前提是 gcd(nums[i], nums[j]) > 1。判斷是否能透過這些操作將陣列排序為非遞減順序。
解題思路:若兩個數共享質因子,它們可以互換。透過傳遞性,共享相同質因子的所有數屬於同一個連通分量,分量內的數可以任意排列。使用 Union-Find 將每個數與其所有質因子合併。最後檢查:對每個位置 i,nums[i] 和排序後的 sorted[i] 是否在同一連通分量中。若是,則可排序。
C++ 解法
複雜度分析
時間複雜度:O(M log log M + n log M) — 篩法 O(M log log M),質因數分解每個數 O(log M),Union-Find 操作近乎 O(1)。M = max(nums)。
空間複雜度:O(M) — 篩法陣列和 Union-Find 陣列。
虛擬碼
1. Compute smallest prime factor (SPF) sieve up to max(nums) 2. Initialize Union-Find with max(nums)+1 elements 3. For each number x in nums: a. Factorize x using SPF sieve b. Union(x, each prime factor of x) 4. Sort a copy of nums 5. For each position i: a. If Find(nums[i]) != Find(sorted[i]): return false 6. Return true
其他解法
直接 GCD 圖 + BFS/DFS:對每對元素計算 GCD,GCD > 1 則加邊,用 BFS 找連通分量。時間 O(n^2 log M),n 大時過慢。
質因數分組:用雜湊表按質因子分組,同組的數可互換。需要合併共享質因子的組。等價於 Union-Find 解法但用不同視角實作。
延伸思考
- 若交換條件改為 lcm(nums[i], nums[j]) <= threshold,問題如何變化?
- 若要求最少交換次數使陣列排序,如何計算?
- 若陣列可以有重複元素,解法是否需要修改?