leetcode:765. 情侣牵手【配对问题 + 贪心策略】

136 阅读 0 评论 90 点赞

我是靠谱客的博主阳光人生，这篇文章主要介绍leetcode:765. 情侣牵手【配对问题 + 贪心策略】，现在分享给大家，希望可以做个参考。

在这里插入图片描述

分析

想不到办法就贪心
固定左边的，然后找到右边的位置，移动一次即可
需要记录每个人对应的位置，然后更新交换后的位置和row即可

ac code

复制代码

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
class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        # 考虑even的idx，然后让odd的匹配（贪心策略）
        # 不动even 只动odd
        indices = {x : i for i, x in enumerate(row)}
        ans = 0
        n = len(row)
        for i in range(n // 2):
            x = row[2 * i]
            # find partner
            if x % 2 == 0:
                y = x + 1
            else:
                y = x - 1
            if indices[y] != 2 * i + 1:
                ans += 1
                changer = row[2 * i + 1]
                changer_idx = indices[y]
                # change
                row[2 * i + 1], row[changer_idx] = y, changer 
                indices[y] = 2 * i + 1
                indices[changer] = changer_idx
                
            #print(indices)
        return ans