运动员和训练师的最大匹配数
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
为什么在双指针遍历中,即使当前运动员的能力值大于当前训练师的能力值,训练师指针也总是向右移动?
▷🦆
在解题思路中提到对数组进行排序,排序后如何保证运动员和训练师之间的最优匹配仍然可以实现?
▷🦆
在算法中提到,如果当前运动员能力值小于等于当前训练师能力值时,运动员指针会右移并增加匹配数。那么,这种方法是否可能错过某些潜在的更优匹配?
▷