#Problem

#⭐️⭐️⭐️⭐️

Couples holding hands.

给一个array有2N个数表示N对couple, couple的定义就是(1,2)是couple, (3,4)是couple. 因为array是unsorted, 问要经过几次swap才能把所有的couple都挨在一起. 比如[1,2,3,4]或者[4,3,1,2]都是合理的结果.

#Solution

#Solution #1 - Greedy

不停的Swap就好了. 不知道怎么证明.. 太懒了… 下次有空的话研究第二种solution吧 orz..

#Solution #2 - TODO

https://leetcode.com/articles/couples-holding-hands/

#Code

#Greedy - Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int minSwapsCouples(int[] rows) {
if (rows == null || rows.length == 0) return 0;
final Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < rows.length; i++) {
indexMap.put(rows[i], i);
}
int res = 0;
int i = 0;
while (i < rows.length - 1) {
final int other = rows[i] % 2 == 0 ? rows[i] + 1 : rows[i] - 1;
final int otherPos = indexMap.get(other);
if (otherPos != i + 1) {
swap(rows, indexMap, otherPos, i + 1);
res++;
}
i += 2;
}
return res;
}
private void swap(final int[] rows, final Map<Integer, Integer> indexMap, final int i, final int j) {
final int tmp = rows[i];
rows[i] = rows[j];
rows[j] = tmp;
indexMap.put(rows[i], i);
indexMap.put(rows[j], j);
}
}

Comments