题目描述

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

算法1

(暴力枚举) $O(n^2)$

找规律
循环号与位置下标之间的规律
0(对应第0,1位的元素) 1(对应2,3)
2(对应4，5) 3(对应6,7)
4(对应8,9) 5(对应10,11) 6(对应12,13)
每次循环我们取2个元素,一共取N次，2个元素下标可以通过2i ,2i+1得到

下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13
序号 3 2 0 1 4 6 5 7 8 12 13 11 9 10
时间复杂度分析： $O(n^2)$,

可以用一个哈希表存储位置，这样交换就只用O(1)的时间,那么时间复杂度O(n)了

python 代码

class Solution(object):
    def minSwapsCouples(self, row):
        """
        :type row: List[int]
        :rtype: int


        3 2 0 1  4 6 5 7   8 12   13 11   9 10
        """
        res = 0
        for i in range( len(row)// 2 - 1 ):
                a = row[2*i]
                b = row[2*i+1]
                if not ((a & 1 and b==a-1) or (b & 1 and a+1==b)):

                    if a & 1:
                        for j in range(2*i+2, len(row)):   
                            if row[j] == a-1:
                                row[2*i+1], row[j] = row[j], row[2*i+1]
                                res += 1
                                break
                    else:
                        for j in range(2*i+2, len(row)):
                            if row[j] == a+1:
                                row[2*i+1], row[j] = row[j], row[2*i+1]
                                res += 1
                                break
        return res