765. Couples Holding Hands

▶ n 对夫妻共 2n 个人随机坐成一排，“交换其中某两人的位置” 称为一次操作，求最少的操作此次数，使 n 对夫妻两人都相邻。初始座位为非负整数列 D₁^n-1，其中值为 2k 和 2k+1 的两个元素为一对夫妻。（本体尚未有 Discuss或 Solution）

● 代码，2 ms，顺着梳理

 1 class Solution
 2 {
 3 public:
 4     int minSwapsCouples(vector<int>& row)
 5     {
 6         int i, len;
 7         for (i = len = 0; i < row.size(); row[i++] /= 2);       // 值相等的元素为一对夫妻
 8         for (auto it = row.begin(); it != row.end(); it += 2)   // 每次调整一对夫妻
 9         {
10             if (*it != *(it + 1))                               // 只要接下来的两位不是夫妻，则在后面的位置中找到相应的配偶换过来
11             {
12                 iter_swap(it + 1, find(it + 2, row.end(), *it));
13                 len++;
14             }
15         }
16         return len;
17     }
18 };

● 代码，4 ms，建立映射表

 1 class Solution
 2 {
 3 public:
 4     void insert_helper(unordered_map<int, int>& m, int v1, int v2)// 接受两个元素的组好，映射表 m 相当于需要调整的次数
 5     {
 6         auto k = min(v1, v2), v = max(v1, v2);
 7         if (k != v)
 8         {
 9             if (m.count(k) > 0)
10                 insert_helper(m, m[k], v);
11             else
12                 m[k] = v;
13         }
14         return;
15     }
16     int minSwapsCouples(vector<int>& row)
17     {
18         unordered_map<int, int> m;
19         for (auto i = 0; i < row.size(); i += 2)
20             insert_helper(m, row[i] / 2, row[i + 1] / 2);
21         return m.size();
22     }
23 };