各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 21 天。今天力扣上的每日一题是「765. 情侣牵手」。

解题思路

题目的意思是说 $(0, 1)$是一对情侣👫，$(2,3)$ 是一对情侣👫，……$(2N -2, 2N - 1)$是一对情侣👫，通过对数组最少的交换次数，使得所有情侣👫的位置都相邻。（情侣牵手是 Hard 问题）

贪心

这题使用贪心是最简单的方法。该策略是说，我们遍历每个偶数位置$2 i$ ，把它的对象安排到它右边的奇数位置 $2 i + 1$。

我们看个动图来说明此过程。

765.gif
怎么证明该贪心策略是正确的呢？博主也没想到，欢迎大家留言讨论。

代码

求数字 $x$ 的对象时用到了一个技巧，$x$的对象是$x ^ 1$。解释如下：

  • 当 $x$ 是偶数，则其二进制的末尾是 0，所以 $x ^ 1$ 将其二进制的末尾改成 1，于是得到了$x$的对象 $x + 1$。
    - 当 $x$ 是奇数，则其二进制的末尾是 1，所以 $x ^ 1$ 将其二进制的末尾改成 0，于是得到了$x$的对象 $x - 1$。

对应的 Python 代码如下：

  1. class Solution(object):
  2.     def minSwapsCouples(self, row):
  3.         """
  4.         :type row: List[int]
  5.         :rtype: int
  6.         """
  7.         N = len(row)
  8.         res = 0
  9.         for i in range(0, N - 1, 2):
  10.             if row[i] == row[i + 1] ^ 1:
  11.                 continue
  12.             for j in range(i + 1, N):
  13.                 if row[i] == row[j] ^ 1:
  14.                     row[i + 1], row[j] = row[j], row[i + 1]
  15.             res += 1
  16.         return res

时间复杂度：$O(N ^ 2)$，题目给出的 len(row) 在 60 以内，耗时 24 ms。
空间复杂度：$O(1)$，内存消耗 12.8M。

刷题心得

  1. 今天的情侣牵手的问题，有比较多的方法，最简单的方法是贪心。但是很难证明正确性。
    2. 位运算是神器，异或是神器中的神器，推荐阅读 liuyubobo老师的文章：真实世界的异或运算。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！