leetcode
leetcode 2101 ~ 2150
运动员和训练师的最大匹配数

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

难度:

标签:

题目描述

代码结果

运行时间: 108 ms, 内存: 31.3 MB


/*
 思路:
 1. 使用 Java Stream 对 players 和 trainers 数组进行排序。
 2. 使用双指针遍历两个数组,同时通过过滤和计数匹配成功的情况。
 3. 如果当前的运动员能够匹配当前的训练师,则计数增加,并同时移动两个指针。
 4. 最终返回匹配的最大数量。
 */
import java.util.Arrays;

public class Solution {
    public int maxMatching(int[] players, int[] trainers) {
        int[] sortedPlayers = Arrays.stream(players).sorted().toArray();
        int[] sortedTrainers = Arrays.stream(trainers).sorted().toArray();
        int i = 0, j = 0, matches = 0;
        while (i < sortedPlayers.length && j < sortedTrainers.length) {
            if (sortedPlayers[i] <= sortedTrainers[j]) {
                matches++;
                i++;
                j++;
            } else {
                j++;
            }
        }
        return matches;
    }
}

解释

方法:

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

时间复杂度:

O(n log n + m log m)

空间复杂度:

O(log n + log m)

代码细节讲解

🦆
为什么在双指针遍历中,即使当前运动员的能力值大于当前训练师的能力值,训练师指针也总是向右移动?
这是因为如果当前运动员的能力值大于当前训练师的能力值,那么这名运动员无法与这名训练师匹配。因为训练师的能力值已经无法满足这名运动员,所以需要移动训练师指针,以寻找下一名可能的训练师。保持运动员指针不动,是因为这名运动员可能与后续的某位训练师能力值匹配。
🦆
在解题思路中提到对数组进行排序,排序后如何保证运动员和训练师之间的最优匹配仍然可以实现?
通过将运动员和训练师数组进行排序,可以确保两者的能力值都按升序排列。这样,使用双指针方法从最小值开始匹配,可以保证每次都将当前可用的最小能力的运动员与足够资格的最小能力的训练师进行匹配。这种贪心策略,即每次选择当前可行的最小匹配,可以确保获得最大的匹配数量,因为它允许保留较高能力的训练师以备后续较高能力的运动员匹配。
🦆
在算法中提到,如果当前运动员能力值小于等于当前训练师能力值时,运动员指针会右移并增加匹配数。那么,这种方法是否可能错过某些潜在的更优匹配?
这种方法不会错过更优的匹配。由于数组是排序的,当前的匹配策略是将当前可用的最小能力的运动员匹配给足以满足其能力的最小训练师。这保证了每次匹配都是在当前情况下最优的,因为更强的训练师能够保留给需要更高能力值的运动员。这样的贪心策略确保了在整体上实现最大的匹配数,而不是单个匹配的最优选择。

相关问题