LeetCode 题解工作台
运动员和训练师的最大匹配数
给你一个下标从 0 开始的整数数组 players ，其中 players[i] 表示第 i 名运动员的 能力 值，同时给你一个下标从 0 开始的整数数组 trainers ，其中 trainers[j] 表示第 j 名训练师的 训练能力值 。 如果第 i 名运动员的能力值 小于等于 第 j 名训练…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
根据题目描述，每位运动员应该尽可能匹配能力值最接近的训练师，因此我们可以对运动员和训练师的能力值进行排序，然后使用双指针的方法进行匹配。 我们用两个指针 和 分别指向运动员和训练师的数组，初始时都指向数组的起始位置。然后我们逐个遍历运动员的能力值，如果当前训练师的能力值小于当前运动员的能力值，我们就将训练师的指针向右移动一位，直到找到一个能力值大于等于当前运动员的训练师。如果找不到这样的训练师…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个下标从 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 <= 1051 <= players[i], trainers[j] <= 109
解题思路
方法一：贪心 + 双指针
根据题目描述，每位运动员应该尽可能匹配能力值最接近的训练师，因此我们可以对运动员和训练师的能力值进行排序，然后使用双指针的方法进行匹配。
我们用两个指针 和 分别指向运动员和训练师的数组，初始时都指向数组的起始位置。然后我们逐个遍历运动员的能力值，如果当前训练师的能力值小于当前运动员的能力值，我们就将训练师的指针向右移动一位，直到找到一个能力值大于等于当前运动员的训练师。如果找不到这样的训练师，说明当前运动员无法匹配任何训练师，此时我们返回当前运动员的下标即可。否则，，我们可以将当前运动员和训练师匹配，然后将两个指针都向右移动一位。继续这个过程直到遍历完所有的运动员。
如果我们遍历完所有的运动员，说明所有的运动员都能匹配到训练师，此时我们返回运动员的数量即可。
时间复杂度 ，空间复杂度 。其中 和 分别为运动员和训练师的数量。
class Solution:
def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
players.sort()
trainers.sort()
j, n = 0, len(trainers)
for i, p in enumerate(players):
while j < n and trainers[j] < p:
j += 1
if j == n:
return i
j += 1
return len(players)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(m \log m + n \log n) |
| 空间 | O(\log m + \log n) |
面试官常问的追问
外企场景- question_mark
Pay attention to array ordering; an unsorted approach may miss optimal matches.
- question_mark
Demonstrate correct two-pointer increments and match counting.
- question_mark
Explain why using the smallest suitable trainer ensures maximum matches.
常见陷阱
外企场景- error
Not sorting the arrays can lead to suboptimal matchings.
- error
Incrementing only one pointer incorrectly can skip valid pairings.
- error
Failing to track which players or trainers are already matched.
进阶变体
外企场景- arrow_right_alt
Consider a variant where each trainer can train multiple players, requiring adjusted pointer logic.
- arrow_right_alt
A version where players have minimum and maximum acceptable trainer capacities changes the greedy invariant.
- arrow_right_alt
Randomly shuffled arrays with large input sizes test the efficiency of sorting plus two-pointer scan.