title

problem link

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:Input: row = [0, 2, 1, 3] Output: 1 Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:Input: row = [3, 2, 0, 1] Output: 0 Explanation: All couples are already seated side by side.

Note:

len(row) is even and in the range of [4, 60]. row is guaranteed to be a permutation of 0…len(row)-1.

N对夫妇坐在2N个排成一排的座位上. 现求最小的交换数量，使每对夫妇并坐一起，他们可以手牵着手。

一次交换可选择任何两个人交换座位。

人和座位由从0到2N-1的整数表示，夫妻按顺序编号，第一对是(0,1)，第二对是(2,3)，以此类推，最后一对是(2N-2,2N-1)。

初始座位由row [i]给出，表示坐在第i座位的人的编号。

solution

找出第偶数个位置是否和他的另一半在一起，是的话不用交换，否则找出另一半在哪里， 然后直接把现在和自己坐在一起的人与自己的另一半的位置交换即可。

o(n), o(n)

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        from collections import defaultdict
        num2i = defaultdict(int)
        for i, iter in enumerate(row):
            num2i[iter] = i
        n = len(row)
        res = 0

        def swap(i, j):
            row[i], row[j] = row[j], row[i]
            num2i[row[j]] = j
            num2i[row[i]] = i
            nonlocal res
            res += 1

        for i in range(1, n, 2):
            partner = row[i] - 1
            if row[i] % 2 == 0:
                partner = row[i] + 1
            if partner == row[i - 1]:
                continue
            swap(i-1, num2i[partner])
        # print(row)
        return res

UF方法

参考

把couple当作一个点，共有N个点，a[0],a[1]它都表示一个点，因此如果两个点分开了就代表它们和别的点相连了，因此求连通图数量k, N-k就是想要的结果。

Think about each couple as a vertex in the graph. So if there are N couples, there are N vertices. Now if in position 2i and 2i +1 there are person from couple u and couple v sitting there, that means that the permutations are going to involve u and v. So we add an edge to connect u and v. The min number of swaps = N - number of connected components. This follows directly from the theory of permutations. Any permutation can be decomposed into a composition of cyclic permutations. If the cyclic permutation involve k elements, we need k -1 swaps. You can think about each swap as reducing the size of the cyclic permutation by 1. So in the end, if the graph has k connected components, we need N - k swaps to reduce it back to N disjoint vertices.

Then there are many ways of doing this. We can use dfs for example to compute the number of connected components. The number of edges isn O(N). So this is an O(N) algorithm. We can also use union-find. I think a union-find is usually quite efficient. The following is an implementation.

class Solution {
    private class UF {
        private int[] parents;
        public int count;
        UF(int n) {
            parents = new int[n];
            for (int i = 0; i < n; i++) {
                parents[i] = i;
            }
            count = n;
        }
        
        private int find(int i) {
            if (parents[i] == i) {
                return i;
            }
            parents[i] = find(parents[i]);
            return parents[i];
        }
        
        public void union(int i, int j) {
            int a = find(i);
            int b = find(j);
            if (a != b) {
                parents[a] = b;
                count--;
            }
        }
    }
    public int minSwapsCouples(int[] row) {
        int N = row.length/ 2;
        UF uf = new UF(N);
        for (int i = 0; i < N; i++) {
            int a = row[2*i];
            int b = row[2*i + 1];
            uf.union(a/2, b/2);
        }
        return N - uf.count;
    }
}