文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题运动员和训练师的最大匹配数出处2410. 运动员和训练师的最大匹配数难度3 级题目描述要求给定一个下标从0 \texttt{0}0开始的整数数组players \texttt{players}players其中players[i] \texttt{players[i]}players[i]表示第i \texttt{i}i名运动员的能力值另外给定一个下标从0 \texttt{0}0开始的整数数组trainers \texttt{trainers}trainers其中trainers[j] \texttt{trainers[j]}trainers[j]表示第j \texttt{j}j名训练师的训练能力值。如果第i \texttt{i}i名运动员的能力值小于等于第j \texttt{j}j名训练师的能力值那么第i \texttt{i}i名运动员可以匹配第j \texttt{j}j名训练师。每名运动员至多可以匹配一名训练师每名训练师最多可以匹配一名运动员。返回满足上述要求的players \texttt{players}players和trainers \texttt{trainers}trainers的最大匹配数。示例示例 1输入players [4,7,9], trainers [8,2,5,8] \texttt{players [4,7,9], trainers [8,2,5,8]}players [4,7,9], trainers [8,2,5,8]输出2 \texttt{2}2解释得到两个匹配的一种方案是players[0] \texttt{players[0]}players[0]与trainers[0] \texttt{trainers[0]}trainers[0]匹配因为4 ≤ 8 \texttt{4} \le \texttt{8}4≤8。players[1] \texttt{players[1]}players[1]与trainers[3] \texttt{trainers[3]}trainers[3]匹配因为7 ≤ 8 \texttt{7} \le \texttt{8}7≤8。可以证明2 \texttt{2}2是可以形成的最大匹配数。示例 2输入players [1,1,1], trainers [10] \texttt{players [1,1,1], trainers [10]}players [1,1,1], trainers [10]输出1 \texttt{1}1解释训练师可以匹配所有3 \texttt{3}3个运动员。只能有一个运动员匹配一个训练师所以最大答案是1 \texttt{1}1。数据范围1 ≤ players.length, trainers.length ≤ 10 5 \texttt{1} \le \texttt{players.length, trainers.length} \le \texttt{10}^\texttt{5}1≤players.length, trainers.length≤1051 ≤ players[i], trainers[j] ≤ 10 9 \texttt{1} \le \texttt{players[i], trainers[j]} \le \texttt{10}^\texttt{9}1≤players[i], trainers[j]≤109解法思路和算法为了使匹配数最大根据贪心思想应按照运动员的能力值递增的顺序依次匹配每个运动员对于每个运动员选择剩余训练师中能匹配该运动员的训练能力值最小的训练师与该运动员匹配理由如下。将数组players \textit{players}players按升序排序之后假设存在两个相邻运动员的能力值分别是player 1 \textit{player}_1player1​和player 2 \textit{player}_2player2​其中player 1 ≤ player 2 \textit{player}_1 \le \textit{player}_2player1​≤player2​可以匹配这两个运动员的训练能力值最小的训练师的训练能力值分别是trainer 1 \textit{trainer}_1trainer1​和trainer 2 \textit{trainer}_2trainer2​则必有trainer 1 ≤ trainer 2 \textit{trainer}_1 \le \textit{trainer}_2trainer1​≤trainer2​。当匹配的运动员最多时应将trainer 1 \textit{trainer}_1trainer1​匹配player 1 \textit{player}_1player1​将trainer 2 \textit{trainer}_2trainer2​匹配player 2 \textit{player}_2player2​。假设匹配player 1 \textit{player}_1player1​的训练师的训练能力值是trainer 3 \textit{trainer}_3trainer3​且trainer 3 trainer 1 \textit{trainer}_3 \textit{trainer}_1trainer3​trainer1​考虑以下两种情况。当trainer 3 trainer 2 \textit{trainer}_3 \textit{trainer}_2trainer3​trainer2​时仍可以将trainer 2 \textit{trainer}_2trainer2​匹配player 2 \textit{player}_2player2​其余能力值更大的运动员的可用训练师数量不变可以匹配的运动员数量不变。当trainer 3 ≥ trainer 2 \textit{trainer}_3 \ge \textit{trainer}_2trainer3​≥trainer2​时其余能力值更大的运动员的可用训练师数量不变或减少一位因此可以匹配的运动员数量不变或减少不可能匹配更多的运动员。因此对于每个运动员选择剩余训练师中能匹配该运动员的最小训练能力值的训练师与该运动员匹配该贪心策略可以匹配最多数量的运动员。具体做法是首先将数组players \textit{players}players和trainers \textit{trainers}trainers按升序排序然后使用双指针遍历两个数组对于每个players [ i ] \textit{players}[i]players[i]找到未匹配的训练师下标中满足trainers [ j ] ≥ players [ i ] \textit{trainers}[j] \ge \textit{players}[i]trainers[j]≥players[i]的最小下标j jj则trainers [ j ] \textit{trainers}[j]trainers[j]可以匹配players [ i ] \textit{players}[i]players[i]。由于数组players \textit{players}players和trainers \textit{trainers}trainers已经按升序排序因此遍历数组players \textit{players}players的顺序为运动员的能力值递增顺序可以匹配运动员的训练师的最小训练能力值也是递增的和遍历数组trainers \textit{trainers}trainers的顺序相同只要遍历两个数组各一次即可得到最大匹配数。代码classSolution{publicintmatchPlayersAndTrainers(int[]players,int[]trainers){intmatches0;Arrays.sort(players);Arrays.sort(trainers);intnumOfPlayersplayers.length,numOfTrainerstrainers.length;intplayerIndex0,trainerIndex0;while(playerIndexnumOfPlayerstrainerIndexnumOfTrainers){if(players[playerIndex]trainers[trainerIndex]){matches;playerIndex;}trainerIndex;}returnmatches;}}复杂度分析时间复杂度O ( m log ⁡ m n log ⁡ n ) O(m \log m n \log n)O(mlogmnlogn)其中m mm和n nn分别是数组players \textit{players}players和trainers \textit{trainers}trainers的长度。两个数组排序分别需要O ( m log ⁡ m ) O(m \log m)O(mlogm)和O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间排序之后使用双指针遍历两个数组需要O ( m n ) O(m n)O(mn)的时间因此时间复杂度是O ( m log ⁡ m n log ⁡ n m n ) O ( m log ⁡ m n log ⁡ n ) O(m \log m n \log n m n) O(m \log m n \log n)O(mlogmnlognmn)O(mlogmnlogn)。空间复杂度O ( log ⁡ m log ⁡ n ) O(\log m \log n)O(logmlogn)其中m mm和n nn分别是数组players \textit{players}players和trainers \textit{trainers}trainers的长度。两个数组排序分别需要O ( log ⁡ m ) O(\log m)O(logm)和O ( log ⁡ n ) O(\log n)O(logn)的递归调用栈空间。