765. Couples Holding Hands

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:

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

2. row is guaranteed to be a permutation of 0...len(row)-1.

利用數字間的XOR找到該在一起的pair，例如0^0x1之後是1，1＾0x1之後是0，所以0和1是一組。和0x1做XOR可以把奇偶數互換。

// Greedy
int minSwapsCouples(vector<int>& row) { // time: O(n^2); space: O(1)
    int res = 0, n = row.size();
    for (int i = 0; i < n - 1; i += 2) {
        if (row[i + 1] == (row[i] ^ 1)) continue;
        ++res;
        for (int j = i + 1; j < n; ++j) {
            if (row[j] == (row[i] ^ 1)) {
                swap(row[i + 1], row[j]);
                break;
            }
        }
    }
    return res;
}

原本有獨立的n/2個group，每遇到一個root值不相等的兩個數，就把他們之間連結起來，代表需要這兩個數的group有需要swap，一開始cnt設為n/2，代表有多少個連結起來的group，最後再用n/2減去這個數量就是需要做的交換次數。

// Union Find
int find(vector<int>& root, int i) {
    return (i == root[i]) ? i : root[i] = find(root, root[i]);
}
int minSwapsCouples(vector<int>& row) { // time: O(log*(n)); space: O(n)
    int res = 0, n = row.size(), cnt = n / 2;
    vector<int> root(cnt, 0);
    for (int i = 0; i < cnt; ++i) root[i] = i;
    for (int i = 0; i < n - 1; i += 2) {
        int x = find(root, row[i] / 2);
        int y = find(root, row[i + 1] / 2);
        if (x != y) {
            root[x] = y;
            --cnt;
        }
    }
    return n / 2 - cnt;
}

概念上類似Union Find，但這個解法是用hashmap來實現。

// Similar Union Find by Hashmap
void helper(unordered_map<int, int>& m, int x, int y) {
    int c1 = min(x, y), c2 = max(x, y);
    if (c1 == c2) return;
    if (m.count(c1)) helper(m, m[c1], c2);
    else m[c1] = c2;
}
int minSwapsCouples(vector<int>& row) { // time: O(n); space: O(n)
    unordered_map<int, int> m;
    for (int i = 0; i < row.size(); i += 2) {
        helper(m, row[i] / 2, row[i + 1] / 2);
    }
    return m.size();
}

int minSwapsCouples(vector<int>& row) { // time: O(n); space: O(n)
    int res = 0, n = row.size();
    vector<int> ptn(n, 0), pos(n, 0);
    for (int i = 0; i < n; ++i) {
        ptn[i] = i % 2 == 0 ? i + 1 : i - 1;
        pos[row[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = ptn[pos[ptn[row[i]]]]; j != i; j = ptn[pos[ptn[row[i]]]]) {
            swap(row[i], row[j]);
            swap(pos[row[i]], pos[row[j]]);
            ++res;
        }
    }
    return res;
}