765 Couples Holding Hands

765. Couples Holding Hands

1. Question

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. Aswapconsists of choosinganytwo people, then they stand up and switch seats.

The people and seats are represented by an integer from0to2N-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 byrow[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:

1. len(row)is even and in the range of[4, 60].

2. rowis guaranteed to be a permutation of0...len(row)-1.

2. Implementation

(1) Union Find

思路: 我们可以想像每对couple是图的一个点，如果在[2 * i, 2 * i + 1]两个位置上的人分别来自于couple A组，和couple B组，那么我们就将它们联合起来组成一个组，这意味着我们可以用union find解决这个问题。假设我们有N组couple， union find的count刚开始也是N，swap的次数就等于count减少的次数，也就是 N - uf.count. 这里要注意的数，对于给定的一个人 row[i]，我们通过除以2, 判断这个人应该属于哪一组couple， 比如0, 1属于组0， 2和3属于组1, 如此类推。

class Solution {
    public int minSwapsCouples(int[] row) {
        int N = row.length / 2;

        UF uf = new UF(N);

        for (int i = 0; i < N; i++) {
            int num1 = row[2 * i];
            int num2 = row[2 * i + 1];
            uf.union(num1 / 2, num2 / 2);
        }
        return N - uf.count;
    }

    class UF {
        int[] parents;
        int[] size;
        int count;

        public UF(int n) {
            parents = new int[n];
            size = new int[n];
            count = n;

            for (int i = 0; i < n; i++) {
                parents[i] = i;
                size[i] = 1;
            }
        }

        public int find(int i) {
            while (i != parents[i]) {
                i = parents[i];
            }
            return i;
        }

        public void union(int i, int j) {
            int p1 = find(i);
            int p2 = find(j);

            if (p1 == p2) {
                return;
            }

            if (size[p1] < size[p2]) {
                parents[p1] = p2;
                size[p2] += p1;
            }
            else {
                parents[p2] = p1;
                size[p1] += size[p2];
            }
            --count;
        } 
    }
}

3. Time & Space Complexity

(1) Union Find: 时间复杂度O(n), n是couple的个数，空间复杂度O(n)