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 choosing any two 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) 利用pos数组，记录row[i]在row的位置

(2) 对于每对couple，我们可以发现它们的值除以2是一样的，比如(2, 3) 两个数除以2都为1, (6,7)两个除以2为3，我们可以根据这个判断当前的row[i] 和 row[i + 1]是否为couple，如果是则跳过，无需swap

(3) 如果row[i] 和 row[i + 1]不是couple的话，则我们要找到row[i]的partner。如果row[i]是偶数的话，则它的partner是奇数, 其值是 row[i]/2 * 2 + 1，通过pos数组我们可以知道partner的位置。类似的道理，如果row[i]是奇数的话，它的partner是偶数，其值是row[i]/2 * 2

(4) 找到row[i] partner位置后，我们需要更新pos[row[i+ 1]]的值为row[i] partner的位置，然后再将row[i + 1]和row[partnerIndex]的值交换。注意这两步不能倒过来，否则当我们交换了row[i + 1]和row[partnerIndex]的值后，再更新pos[row[i + 1]]的值时，row[i + 1]的值已经是row[i]的partner，而不是原来的row[i + 1]对应的数

class Solution {
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int[] pos = new int[n];

        for (int i = 0; i < n; i++) {
            pos[row[i]] = i;
        }

        int res = 0;

        for (int i = 0; i < n; i += 2) {
            // 如果已经组成一对couple， 无需swap
            if (row[i]/2 == row[i + 1]/2) continue;

            int partnerIndex = 0;
            if (row[i] % 2 == 0) {
                partnerIndex = pos[row[i]/2 * 2 + 1];
            }
            else {
                partnerIndex = pos[row[i]/2 * 2];
            }

            // update pos array
            pos[row[i + 1]] = partnerIndex;

            // swap position of row[i + 1] and row[partnerIndex] to make couple
            swap(row, i + 1, partnerIndex);
            ++res;
        }
        return res;
    }

    public void swap(int[] row, int i, int j) {
        int temp = row[i];
        row[i] = row[j];
        row[j] = temp;
    }
}

3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(n)