765.couples_holding_hands.md

765.couples_holding_hands

1. 描述
   • N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。 人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。 这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
   • 示例 1: 输入: row = [0, 2, 1, 3] 输出: 1 解释: 我们只需要交换row[1]和row[2]的位置即可。
   • 示例 2: 输入: row = [3, 2, 0, 1] 输出: 0 解释: 无需交换座位，所有的情侣都已经可以手牵手了。
   • 说明: len(row) 是偶数且数值在 [4, 60]范围内。 row 是序列 0...len(row)-1 的一个全排列。
2. 分析
   • 一，问题简化 N对couple 在2N个人里，坐错位置的两个人，连接一条边。假设所有的边连好了，构成K个连通分支（集合，错误环） 最小交换次数 = N - K 所以，本题可以简化为，怎样计算这个K。 这里使用并查集的思路。具体如下。
   • 二，具体例子
     • couple: 0 1 2 3 4 5 6 7 8 9
     • couple identifier: 0 0 1 1 2 2 3 3 4 4
     • 2i和2i+1位置上的值，除以2取整。如果两个值一样，则他们是一对。 如果不是，他们不是一对，把他们所在的集合合并（union）在一起。（初始状态是，自己是一个集合）
     • 这是一个小动画。可点击下载。765_holdingHands
   • 三，can it be faster？
     可以。在union操作中，小集合“贴”到大集合里。
3. 实现

class Solution {
public:
    // 第一次错误：这个函数没写好
    int find_root(int* connected_component, int person) //有点像哈希表。。
    {
        int mom = connected_component[person];        
        while(mom >=0 ) 
        {
            person = mom;
            mom = connected_component[mom];
        }
        return person;
    }
    int minSwapsCouples(vector<int>& row) {
        int i, N = row.size()/2;
        int k = N;
        // 用couple identifier初始化connected_component
        // 即N个连通分支  
        // connected_component里面，如果自己是根，值就是负数。绝对值表示自己连通分支下元素的个数
        // 如果自己不是根，那么值就是所属连通分支的值     
        int connected_component[N];
        for(i=0; i<N; i++)  connected_component[i]= -1;     //自己和自己是连通的，元素个数是1
        int id1, id2;
        for(i=0; i<N; i++)
        {
            id1 = find_root(connected_component, row[2*i]/2);    //查找row[2*i]/2是属于哪个集合,返回值是集合的根节点
            id2 = find_root(connected_component, row[2*i+1]/2);  //同上
            // 下面是union操作
            if(id1 != id2)
            {
                // 小集合贴到大集合里(加速操作)
                if(connected_component[id1] > connected_component[id1])
                {
                    connected_component[id2] = id1;
                }
                else{
                    connected_component[id1] = id2;
                }
                k --;
            }
        }

        return N-k;
    }
};