LeetCode——情侣牵手

题目描述

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 的一个全排列。

并查集（From 《挑战程序设计竞赛》）

并查集是一种处理元素分组情况的数据结构。并查集可进行如下操作：

查询两个元素是否属于同一组。
合并两个元素所在的组。

并查集使用树形结构：每个组对应一颗树，每个元素对应一个节点。哪个节点作为根节点无需关注，整体组成一棵树即可。

相关操作：

初始化：每个节点作为一棵树。
合并：从一颗树的根向另一颗树的根连边，合并为一棵树，即一棵树作为另一棵树的子树。
查询：沿着树向上走，查询包含这个元素的根节点。如果两个元素具有相同的根节点，则两个元素属于同一组。
优化：
- 合并时，高度小的树作为高度大的树的子树。确保最终的树的高度尽可能小。
- 路径压缩：所有节点直接指向根节点，即树的高度为2。

并查集的实现：

class Union{
    // 每个元素的根
    private int[] parent;
    // 并查集中分组个数
    private int count;

    // 初始化
    Union(int count){
        this.count=count;
        parent=new int[count];
        for(int i=0;i<count;++i){
            parent[i]=i;
        }
    }

    // 查询元素所在树的根
    public int findParent(int n){
        // 自己是自己的parent，即：自己的树的根
        while(n!=parent[n]){
            parent[n]=parent[parent[n]];// 压缩：同一集合中的所有元素指向同一个parent。
            n=parent[n];
        }
        return n;
    }

    // 合并元素x和y所属的组
    public void union(int x,int y){
        int parentX=findParent(x);
        int parentY=findParent(y);
        // 已在同一组
        if(parentX==parentY){
            return;
        }
        // 合并
        parent[parentX]=parentY;
        --count;// 总分组数
    }
}

本题解题思路（参考）

坐错位置的情况与最少需要交换次数：

1对情侣、2个座位，不需要交换。
2对情侣、4个座位，交换1次。
3对情侣、6个座位。首先交换1次使得其中1对情侣坐在一起，剩下2对情侣、4个座位。即需要交换2次。
以此类推，得到f(n)=n-1。即：n对情侣相互坐错位置，最少需要交换n-1次。

把相互坐错位置的情侣放在一组，组内有n对情侣就需要n-1次交换。将N对情侣分为K组：n1,n2...nk，有n1+n2+...+nk=N。需要交换的次数分别为：n1-1、n2-1、...、nk-1，则总的最少交换次数为n1-1+n2-1+...+nk-1=n1+n2+...+nk-k=N-k。则，问题变为：N对情侣，根据相互坐错位置的条件分组，共有多少个分组。

class Solution {
    public int minSwapsCouples(int[] row){
        int maxCount=row.length/2;// 情侣对数
        Union union=new Union(maxCount);
        for(int i=0;i<row.length-1;i+=2){
        // 除2表示属于哪一对情侣（0...n-1）
            union.union(row[i]/2,row[i+1]/2);
        }
        return maxCount-union.count;
    }
    class Union{
        private int[] parent;
        private int count;
        Union(int count){
            this.count=count;
            parent=new int[count];
            for(int i=0;i<count;++i){
                parent[i]=i;
            }
        }

        public int findParent(int n){
            while(n!=parent[n]){
                parent[n]=parent[parent[n]];
                n=parent[n];
            }
            return n;
        }

        public void union(int x,int y){
           int parentX=findParent(x);
            int parentY=findParent(y);
            if(parentX==parentY){
                return;
            }
            parent[parentX]=parentY;
            --count;// 总分组数
        }
    }
}