侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【贪心, 二分查找, 双指针】运动员和训练师的最大匹配数【力扣第 87 场双周赛】

GabrielxD
2022-09-18 / 0 评论 / 0 点赞 / 98 阅读 / 737 字
温馨提示:
本文最后更新于 2022-09-18,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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


给你一个下标从 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 <= 10^5
  • 1 <= players[i], trainers[j] <= 10^9

解题

方法一:贪心 二分查找

思路

若要让运动员匹配上训练师,需要训练师的能力值大于等于运动员的能力值,而每名运动员至多可以匹配一位训练师,那么要保证匹配数尽可能大的话,每位运动员匹配到的训练师的能力值就要在合法的范围内尽可能小(训练师能力值尽可能靠近运动员能力值),这样后面的运动员才会有更多可能的选择。

于是就可以把 trainers 排序然后遍历 players,二分查找 trainers 中第一个大于等于当前运动员能力值的,匹配数加一并从集合中删除该训练师。

代码

class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        int ans = 0;
        multiset<int> st(trainers.begin(), trainers.end());
        for (int& player : players) {
            auto trainer = st.lower_bound(player);
            if (trainer != st.end()) {
                ++ans;
                st.erase(trainer);
            }
        }
        return ans;
    }
};

方法二:排序 双指针

思路

playerstrainers 排序,然后维护两个指针(ij)分别指向这两个数组,i 如果找到了匹配的 j 就向前推,最后 i 是多少就说明匹配成功了多少对。

代码

class Solution {
    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        Arrays.sort(players);
        Arrays.sort(trainers);
        int ans = 0;
        int i = 0, j = 0;
        for (; i < players.length && j < trainers.length; ++i, ++j) {
            int player = players[i];
            while (trainers[j] < player) {
                if (++j >= trainers.length) return i;
            }
        }
        return i;
    }
}
0

评论区