LeetCode 765. Couples Holding Hands题目解析-wowAC

Description

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个凳子上,2N个凳子被安排在一行,第i对夫妇的编号为(2*i-2, 2*i-1),比如第1对夫妇的编号为(0, 1)依次类推,刚开始第i个凳子上坐的人编号为row[i],问最少交换几次可以使得所有夫妇相邻。例如row = [0, 2, 1, 3],只需交换2和1(交换后为row = [0, 1, 2, 3])即可使得所有夫妇相邻。

题目解析

这里有一个O(n)的做法, 一次考虑两个凳子,假设他们不为夫妇,为了让这两个位置坐的恰好是一对夫妇,那么我们就需要调整其中一个人的位置,如此调整直到所有的夫妇相邻,交换的次数就是答案。下面给出证明。

将给定的row抽象成一个n个顶点的无向图(可能包含重边),例如:

(_ _) (_ _) ... (_ _)
(v1 ) (v2 ) ... (vn )

vi和vj之间存在边当且仅当vi和vj中存在一对夫妇,例如vi = (0,2),vj = (1, 4)存在一对夫妇(0, 1),而vi = (0, 2),vj = (1, 3)之间则存在两对夫妇(0, 1)(2, 3),此vi和vj存在重边。

考虑row数组形成的无向图,可以肯定要么是孤立的单个节点,要么是多个孤立的圈,例如row = [0, 1]是一个孤立的点、row = [0, 2, 1, 3]则包含一个圈v1, v2、row = [0, 3, 4, 1, 2, 5, 6, 8, 7, 9],包含两个孤立的圈v1, v2, v3和v4, v5。

对于一个圈来说,假设他有n个节点,那么至少需要n-1次交换即可让每个夫妇相邻。有了这个结论,假定row数组有n个点,m个孤立的圈,那么至少需要n-m次交换即可

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        vector<int> pos(row.size(), 0);  //记录第i个人在row数组中的位置
        for(int i=0; i<row.size(); i++)
            pos[row[i]] = i;
        int res = 0;
        for(int i=0; i<row.size(); i+=2) {
            if(row[i]/2 == row[i+1]/2) continue;  //是夫妇的话不需要调整
            int huswhere = 0;  //假设i是妻子,huswhere是丈夫在row数组中的位置
            if(row[i]%2 == 0) huswhere = pos[row[i]/2*2+1];
            else huswhere = pos[row[i]/2*2];
            res++;
            pos[row[i+1]] = huswhere;          //更新pos数组
            swap(row[i+1], row[huswhere]);

        }
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注