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
解释：
训练师可以与任意一个玩家匹配。
每个玩家只能与一个训练师匹配，所以最大答案是 1 。

提示：

  • 1 <= players.length, trainers.length <= 10^5
  • 1 <= players[i], trainers[j] <= 10^9

解题思路

这是一道典型的贪心算法题目，本质上和分发饼干问题相同。

核心思路： 为了获得最大匹配数，我们应该让能力较弱的玩家优先匹配训练能力较低的训练师，这样可以为能力更强的玩家保留训练能力更高的训练师，从而最大化总匹配数。

算法步骤：

  1. 将玩家数组和训练师数组都按升序排序
  2. 使用双指针技术，分别指向当前考虑的玩家和训练师
  3. 如果当前玩家的能力小于等于当前训练师的训练能力，则匹配成功，两个指针都向前移动
  4. 如果当前玩家的能力大于当前训练师的训练能力，说明该训练师无法训练该玩家，只移动训练师指针
  5. 重复步骤3-4直到某个数组遍历完毕

为什么贪心策略是正确的？ 假设最优解中能力为a的玩家匹配了训练能力为c的训练师，能力为b的玩家匹配了训练能力为d的训练师，其中a < b且d < c。我们可以交换这两个匹配，让能力为a的玩家匹配训练能力为d的训练师，能力为b的玩家匹配训练能力为c的训练师，这样不会减少匹配数，且更符合我们的贪心策略。

代码实现

class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        sort(players.begin(), players.end());
        sort(trainers.begin(), trainers.end());
        
        int i = 0, j = 0, matches = 0;
        
        while (i < players.size() && j < trainers.size()) {
            if (players[i] <= trainers[j]) {
                matches++;
                i++;
            }
            j++;
        }
        
        return matches;
    }
};

class Solution:
    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
        players.sort()
        trainers.sort()
        
        i = j = matches = 0
        
        while i < len(players) and j < len(trainers):
            if players[i] <= trainers[j]:
                matches += 1
                i += 1
            j += 1
        
        return matches

public class Solution {
    public int MatchPlayersAndTrainers(int[] players, int[] trainers) {
        Array.Sort(players);
        Array.Sort(trainers);
        
        int i = 0, j = 0, matches = 0;
        
        while (i < players.Length && j < trainers.Length) {
            if (players[i] <= trainers[j]) {
                matches++;
                i++;
            }
            j++;
        }
        
        return matches;
    }
}

/**
 * @param {number[]} players
 * @param {number[]} trainers
 * @return {number}
 */
var matchPlayersAndTrainers = function(players, trainers) {
    players.sort((a, b) => a - b);
    trainers.sort((a, b) => a - b);
    
    let i = 0, j = 0, matches = 0;
    
    while (i < players.length && j < trainers.length) {
        if (players[i] <= trainers[j]) {
            matches++;
            i++;
        }
        j++;
    }
    
    return matches;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(n log n + m log m)主要消耗在排序上，其中 n 是玩家数量，m 是训练师数量；双指针遍历为 O(n + m)
空间复杂度O(1)只使用了常数个额外变量，排序为原地排序

相关题目