HardRating 1999
765. Couples Holding Hands
greedydepth-first-searchbreadth-first-searchunion-findgraph
解題說明
Couples Holding Hands
題目描述： 有 n 對情侶坐在 2n 個座位上，我們想讓每對情侶都能坐在一起（相鄰的兩個座位）。每次操作可以選擇任意兩個人交換座位，求最少需要多少次交換。情侶的編號規則：(0,1)、(2,3)、(4,5)...即第 i 對情侶的編號為 (2i, 2i+1)。
解題思路：
- 貪心策略：從左到右，每次檢查相鄰兩個座位上的人是否為一對情侶。如果不是，就找到當前位置的人的另一半，將其交換到正確位置。
- 配對規則：對於編號 x，其配偶編號為 x ^ 1（異或 1）。偶數的配偶是下一個奇數，奇數的配偶是前一個偶數。
- 正確性：每次交換至少能配對一對情侶，且不會打破已配對的情侶（因為我們從左到右處理），因此貪心是最優的。
- 也可以用 Union-Find 來思考：每個錯配對形成一個環，環中 k 個錯配需要 k-1 次交換。
C++ 解法
複雜度分析
時間複雜度：O(n) — 遍歷一次座位陣列，每次交換為 O(1)
空間複雜度：O(n) — 用 pos 陣列記錄每個人的位置
虛擬碼
1. Build position array: pos[person] = seat index
2. For each pair of seats (i, i+1):
a. Find the partner of row[i] using XOR: partner = row[i] ^ 1
b. If row[i+1] != partner:
- Find partner's current position j = pos[partner]
- Swap row[i+1] and row[j]
- Update pos array accordingly
- Increment swap counter
3. Return total swaps其他解法
-
Union-Find 方法：將每對座位看作一個節點，將每對情侶的實際座位連邊。連通分量中若有 k 對，需要 k-1 次交換。時間複雜度同為 O(n)，但概念上更直觀地解釋了最少交換次數的本質。
-
環分解法：將錯位的配對關係建成置換圖，計算每個環的大小。一個大小為 k 的環需要 k-1 次交換來解開。這等價於 Union-Find 方法，但直接用 DFS 找環。
延伸思考
- 如果不只是相鄰兩個座位要坐在一起，而是每 k 個人一組呢？如何推廣？
- 如果交換有成本（例如距離越遠成本越高），如何求最小成本？
- 能否用數學方法直接計算答案，而不需要模擬交換過程？