leetcode | 765. Couples Holding Hands
题目
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:
- len(row) is even and in the range of [4, 60].
- row is guaranteed to be a permutation of 0…len(row)-1.
思路与解法
这道题是让我们找到最小的交换次数，来使得所有的夫妻坐在相邻的两个位置上。所以我们可以进行如下处理：
首先，将所有输入数据的奇数进行减1，则最终得到的数据满足每对夫妻有相同的编号。
然后，我们便可以进行遍历，下标i从0开始，依次加2，直到i>=len(row)，然后我们两两进行比较，如果row[i]==row[j]，则表明两者为夫妻，不必进行换座位；否则的话，我们循环向后找到满足row[j]==row[i]的下表j，然后交换row[i+1]和row[j]即可，每交换一次计数器加1，最终返回计数器数值即可。
代码实现
go语言实现如下：
func minSwapsCouples(row []int) int {
couples := len(row)
count := 0
for i:=0; i<couples; i++ {
if row[i]%2==1 {
row[i] -= 1
}
}
for i:=0; i<couples; i+=2 {
if row[i] == row[i+1] {
continue
}
for j:=i+2; j<couples; j++ {
if row[i] == row[j] {
// 利用go语言的赋值语句特性，进行交换操作更加方便
row[i+1], row[j] = row[j], row[i+1]
count++
}
}
}
return count
}