Couples Holding Hands

week 2

题目链接

题目描述

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.

题目分析

这个题意为有N对情侣坐在2N个座位上，但是他们并不是坐在一起的，要使得每一对都能并肩坐在一起，计算最少的交换次数，一次交换可以选择任意的两个人。

情侣按照顺序编号，并不是相连的都是情侣，（0，1），（2，3）等等。由此可知一个偶数的下一个奇数必定是它的另一半。

解题思路

这里的交换有两种可能：

  1. 交换一次后，有两组情侣完成配对。
  2. 交换一次后，仅有一组情侣完成配对，而另一个等待继续交换。

可知如果每一次都是第一种交换的话，则交换次数会比第二种要少，第一种为最佳交换，因此怎么样才能让其先完成第一种匹配呢，我的想法是，既然是第一种，则他们的情侣是交叉坐的，因此若这4个人中有2组情侣，则其和其他组的情侣就没有交集，所以无论如何其它组的情侣如何交换都不会影响到他们。（这里指交换都要匹配成功，如果试图以一次不成功的匹配凑出第一种情况，那么要匹配成功还要交换一次，那么使用第二种也是2次，在次数上是没有任何不同的）

所以我们可以采用贪心算法，遍历每一组，当它的旁边不是它的情侣时，就向后遍历寻找其情侣，进行交换然后匹配成功，这里因为我们发现他们的id的特殊性，可以判断奇偶，快速找到其另一半。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int ans = 0;
        for (int i = 0; i < row.size(); i +=2 )
        {
            int cp;
            if (row[i] % 2 == 0)
            {
                cp = row[i] + 1;//若为偶数则情侣为下一个奇数
            }
            else
            {
                cp = row[i] - 1;//若为奇数则情侣为上一个偶数
            }
            if (row[i + 1] == cp)
            {
                continue;
            }
            ans++;
            for (int j = i + 2; j< row.size(); j++)
            {
                if (row[j] == cp)
                {
                    int temp = row[i+1];
                    row[i+1] = row[j];
                    row[j] = temp;
                    break;
                }
            }
        }
        return ans;
    }
};

总结

当做到这道题目的时候，便想使用贪心算法，但一直都想不清楚如何去证明，后来发现其实他们的交换先后是无关的。
根据网上严谨的证明应该是把row抽象成为一个n个顶点的无向图，每个顶点中为两个人，两个顶点存在边时当且仅当两个顶点中能构成一对情侣，若是第一种情况，则构成重边。
相连的顶点构成圈，圈里面的若为第二种情况，所以对每一个圈来说有n个顶点就至少需要n-1次交换，若为第一种情况，即有重边，只需一次交换，也是n-1（两个顶点，2-1）。
因此若row有n组，m个圈，则至少需要n-m次。这和以上的结论是一样的，因为不同圈之间并不会发生交换。

其它解法

使用哈希配对的方法，两个数均除以2，若相等，则为同一组，若否，则区分出较大和较小的数，若两个数存在联系，则返回，若不存在，则建立这两个数的联系。最后根据哈希表中联系的个数来得到最小交换次数，原理同上面的一样，这里的联系就是指的是顶点之间的边，每个边需要一次交换，重边算作一次，所以每次要判断两个数是否存在联系。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        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();
    }
    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;
    }
};