运动员和训练师的最大匹配数

标签: 贪心 数组 双指针 排序

难度: Medium

给你一个下标从 0 开始的整数数组 players ，其中 players[i] 表示第 i 名运动员的 能力 值，同时给你一个下标从 0 开始的整数数组 trainers ，其中 trainers[j] 表示第 j 名训练师的 训练能力值 。

如果第 i 名运动员的能力值 小于等于 第 j 名训练师的能力值，那么第 i 名运动员可以 匹配 第 j 名训练师。除此以外，每名运动员至多可以匹配一位训练师，每位训练师最多可以匹配一位运动员。

请你返回满足上述要求 players 和 trainers 的 最大 匹配数。

示例 1：

输入：players = [4,7,9], trainers = [8,2,5,8]
输出：2
解释：
得到两个匹配的一种方案是：
- players[0] 与 trainers[0] 匹配，因为 4 <= 8 。
- players[1] 与 trainers[3] 匹配，因为 7 <= 8 。
可以证明 2 是可以形成的最大匹配数。

示例 2：

输入：players = [1,1,1], trainers = [10]
输出：1
解释：
训练师可以匹配所有 3 个运动员
每个运动员至多只能匹配一个训练师，所以最大答案是 1 。

提示：

  • 1 <= players.length, trainers.length <= 105
  • 1 <= players[i], trainers[j] <= 109

Submission

运行时间: 108 ms

内存: 31.3 MB

class Solution:
    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
        players.sort()
        trainers.sort()
        n = len(players)
        m = len(trainers)
        l = 0 
        r = 0
        res = 0
        while l < n and r < m:
            if players[l] <= trainers[r]:
                l += 1
                res += 1
            r += 1
        return res

Explain

此题解采用排序和双指针的方法来寻找最大匹配数。首先，将运动员和训练师的能力值数组分别进行排序。然后使用两个指针分别遍历运动员和训练师数组。通过比较两个数组当前指针指向的值，如果运动员的能力值小于等于训练师的能力值，则表示可以匹配，运动员指针向右移动一位，同时匹配数增加一。无论是否匹配成功，训练师指针都向右移动一位，继续尝试下一个训练师。这个过程持续进行，直到运动员或训练师的数组被完全遍历。

时间复杂度: O(n log n + m log m)

空间复杂度: O(log n + log m)

class Solution:
    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
        players.sort()  # 对运动员能力值排序
        trainers.sort()  # 对训练师能力值排序
        n = len(players)  # 运动员数量
        m = len(trainers)  # 训练师数量
        l = 0  # 运动员的指针
        r = 0  # 训练师的指针
        res = 0  # 匹配数结果
        while l < n and r < m:  # 当两个数组都没有遍历完时
            if players[l] <= trainers[r]:  # 如果当前运动员能力值小于等于当前训练师能力值
                l += 1  # 运动员指针右移
                res += 1  # 匹配数增加
            r += 1  # 训练师指针总是右移
        return res  # 返回最大匹配数

Explore

这是因为如果当前运动员的能力值大于当前训练师的能力值，那么这名运动员无法与这名训练师匹配。因为训练师的能力值已经无法满足这名运动员，所以需要移动训练师指针，以寻找下一名可能的训练师。保持运动员指针不动，是因为这名运动员可能与后续的某位训练师能力值匹配。

通过将运动员和训练师数组进行排序，可以确保两者的能力值都按升序排列。这样，使用双指针方法从最小值开始匹配，可以保证每次都将当前可用的最小能力的运动员与足够资格的最小能力的训练师进行匹配。这种贪心策略，即每次选择当前可行的最小匹配，可以确保获得最大的匹配数量，因为它允许保留较高能力的训练师以备后续较高能力的运动员匹配。

这种方法不会错过更优的匹配。由于数组是排序的，当前的匹配策略是将当前可用的最小能力的运动员匹配给足以满足其能力的最小训练师。这保证了每次匹配都是在当前情况下最优的，因为更强的训练师能够保留给需要更高能力值的运动员。这样的贪心策略确保了在整体上实现最大的匹配数，而不是单个匹配的最优选择。