日期：2026年10月17日
LeetCode 題目連結：3551. Minimum Swaps to Sort by Digit Sum
解題想法
中等難度題。題目給一個長度為 $n ~(1 \leq n \leq 10^5)$ 的整數陣列 $nums ~(1 \leq nums[i] \leq 10^9)$，如果要將 $nums$ 的數字依照數字加總、數字大小由小到大排序，最少要交換 $nums$ 之中任意兩個數字幾次？這題的提示1，先將 $nums$ 依照數字加總、數字大小由小到大排序，再找出排序後的數字在原來的 $nums$ 之中的索引值。提示2，答案等於 $n - $ 環的數量。
對於提示1，我們可以寫一個自訂函式 digit_sum，用來計算整數的數字加總。將 $nums$ 之中的數字加總、數字、索引值組成 tuple 存入另一個陣列 $arr$，再用內建的 sort 將 $arr$ 排序。由於 sort 會自動依照 tuple 的內容及順序由小到大排序，不需要寫比較式。為了找出排序後的數字於 $nums$ 之中對應的索引值，我一開始是用 dict 記錄數字對索引值的資料，但是這樣寫在 C++ 會很慢。後來改成開一個長度 $n$ 的一維陣列 $target$，$target[i]$ 為 $arr[i]$ 在 $nums$ 之中的索引值，這樣速度快很多。
對於提示2，我們可以假設 $nums$ 之中有 $m$ 個環，每個環的長度分別為 $L_1, L_2, \dots, L_m$。如果要將長度為 $L$ 的環排序，交換任意兩個數字 $1$ 次可以將 $1$ 個數字歸位，共要交換 $L - 1$ 次。因此所有環交換的次數為 $$ ans = (L_1 - 1) + (L_2 - 1) + \dots + (L_m - 1) = (L_1 + L_2 + \dots + L_m) - m = n - m $$
Python 程式碼
Runtime: 885 ms, beats 94.69%. Memory: 45.08 MB, beats 75.22%.
class Solution:
def minSwaps(self, nums: List[int]) -> int:
# 自訂函式計算數字加總
def digit_sum(x):
dsum = 0
while x:
dsum += x % 10
x //= 10
return dsum
# 將 {數字加總、num、索引值} 組成 tuple 存入 arr，再由小到大排序
n = len(nums) # 數量
arr = [(digit_sum(nums[i]), nums[i], i) for i, num in enumerate(nums)]
arr.sort()
# 舊的索引值對應到新的索引值
target = [-1] * n
for i in range(n):
target[arr[i][2]] = i
# 找出同組的數字，如果同組有 m 個數字，要交換 m - 1 次
cycle = 0 # 環的數量
visited = [False] * n # nums[i] 是否已經找過
for i in range(n):
if visited[i]: continue
cycle += 1 # 新的環
curr = i
while not visited[curr]:
visited[curr] = True
curr = target[curr]
return n - cycle
