作者： admin

目标

给你一个整数数组 matches 其中 matches[i] = [winneri, loseri] 表示在一场比赛中 winneri 击败了 loseri 。

返回一个长度为 2 的列表 answer ：

• answer[0] 是所有 没有 输掉任何比赛的玩家列表。
• answer[1] 是所有恰好输掉 一场 比赛的玩家列表。

两个列表中的值都应该按 递增 顺序返回。

注意：

• 只考虑那些参与 至少一场 比赛的玩家。
• 生成的测试用例保证 不存在 两场比赛结果 相同 。

示例 1：

输入：matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
输出：[[1,2,10],[4,5,7,8]]
解释：
玩家 1、2 和 10 都没有输掉任何比赛。
玩家 4、5、7 和 8 每个都输掉一场比赛。
玩家 3、6 和 9 每个都输掉两场比赛。
因此，answer[0] = [1,2,10] 和 answer[1] = [4,5,7,8] 。

示例 2：

输入：matches = [[2,3],[1,3],[5,4],[6,4]]
输出：[[1,2,5,6],[]]
解释：
玩家 1、2、5 和 6 都没有输掉任何比赛。
玩家 3 和 4 每个都输掉两场比赛。
因此，answer[0] = [1,2,5,6] 和 answer[1] = [] 。

说明：

• 1 <= matches.length <= 10^5
• matches[i].length == 2
• 1 <= winneri, loseri <= 10^5
• winneri != loseri
• 所有 matches[i] 互不相同

思路

给定一个记录比赛结果的二维数组，数组元素为[winneri, loseri]，求没有输掉任何比赛的玩家以及仅输掉一场比赛的玩家。

简单实现可以直接利用TreeSet保存返回结果，往里面放的时候先判断是否输掉过比赛，如果后面输掉了比赛还要将其从从没输掉比赛的集合中移除。

对于仅输掉一次比赛的集合，不能根据它来判断是否输掉过比赛，因为输掉两次会从集合中移除，如何后续还会输掉比赛，判断集合中没有，就会错误地向其中添加，因此需要额外记录输掉过比赛的集合。

官网题解使用的是哈希表记录失败的次数，效率更高。

代码

/**
 * @date 2024-05-22 9:03
 */
public class FindWinners2225 {

    public List<List<Integer>> findWinners(int[][] matches) {
        List<List<Integer>> res = new ArrayList<>();
        Set<Integer> neverLose = new TreeSet<>();
        Set<Integer> loseOnce = new TreeSet<>();
        Set<Integer> lost = new HashSet<>();
        for (int[] match : matches) {
            int win = match[0];
            int lose = match[1];
            neverLose.remove(lose);
            if (!lost.contains(win)) {
                neverLose.add(win);
            }
            if (!loseOnce.contains(lose) && !lost.contains(lose)) {
                loseOnce.add(lose);
            } else {
                loseOnce.remove(lose);
            }
            lost.add(lose);
        }
        List<Integer> winner = new ArrayList<>(neverLose);
        List<Integer> loser = new ArrayList<>(loseOnce);
        res.add(winner);
        res.add(loser);
        return res;
    }

    public List<List<Integer>> findWinners_v1(int[][] matches) {
        Map<Integer, Integer> loseCnt = new HashMap<>(matches.length);
        for (int[] match : matches) {
            //可以直接在这里记录没有一次失败的
            loseCnt.merge(match[1], 1, Integer::sum);
        }
        List<List<Integer>> res = new ArrayList<>();
        Set<Integer> neverLose = new HashSet<>();
        for (int[] match : matches) {
            if(!loseCnt.containsKey(match[0])){
                neverLose.add(match[0]);
            }
        }
        List<Integer> winner = new ArrayList<>(neverLose);
        Collections.sort(winner);
        List<Integer> lostOnce = loseCnt.entrySet().stream()
                .filter((entry) -> entry.getValue() == 1)
                .map(Map.Entry::getKey).sorted()
                .collect(Collectors.toList());
        res.add(winner);
        res.add(lostOnce);
        return res;
    }
}

性能

暴力解

哈希加排序

目标

你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:

• difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
• worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。

每个工人 最多 只能安排 一个 工作，但是一个工作可以 完成多次 。

• 举个例子，如果 3 个工人都尝试完成一份报酬为 $1 的同样工作，那么总收益为 $3 。如果一个工人不能完成任何工作，他的收益为 $0 。

返回 在把工人分配到工作岗位后，我们所能获得的最大利润 。

示例 1：

输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100 
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

示例 2:

输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
输出: 0

说明:

• n == difficulty.length
• n == profit.length
• m == worker.length
• 1 <= n, m <= 10^4
• 1 <= difficulty[i], profit[i], worker[i] <= 10^5

思路

现在有一组任务，其难度与收益分别使用两个数组 difficulty 与 profit 表示，还有一个数组表示一组工人的能力。现在需要给工人分配工作，如果分配的工作难度大于工人的能力则无法获取收益，求把工人分配到岗后能够获得的最大收益。

我们只需为每个工人分配其能力范围内的收益最高的工作即可。需要注意的是，题目中没有说难度越高收益越高，并且相同难度的收益也会不同。

难度与收益是通过下标关联的，并且是无序的。

一个很自然的想法是维护一个难度与最大收益的映射，然后直接根据工人的能力二分查找相应的收益并累加。

那么如何同时对两个相关联的数组进行排序就是解题的关键。这里直接将 difficulty 与 profit 的映射通过 hashmap 保存起来，然后对 difficulty 从小到大排序。遍历排序后的 difficulty 数组，计算小于该难度的最大收益并更新到profit 中。根据工人的能力二分查找 profit 并累加即可。

容易出错的点是忘记处理相同难度收益不同的情况，二分查找结果为-1时表示无法完成任务任务，不应取难度最低的任务。

官网题解使用的是 javafx.util.Pair/awt包的Point/ 二维数组来保存映射关系。后面收益最高工作的计算，先对 worker 从小到大排序，使用双指针一个指向worker，一个指向难度，后面工人只需从前一个工人的难度开找即可，没用二分查找。

代码

/**
 * @date 2024-05-17 9:20
 */
public class MaxProfitAssignment826 {

    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int res = 0;
        int n = difficulty.length;
        int m = worker.length;
        Map<Integer, Integer> profitMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            // 存在难度相同的，取最大的
            if (profitMap.get(difficulty[i]) == null) {
                profitMap.put(difficulty[i], profit[i]);
            } else {
                profitMap.put(difficulty[i], Math.max(profitMap.get(difficulty[i]), profit[i]));
            }
        }
        Arrays.sort(difficulty);
        // 难度从小到大排，更新对应难度可以获得的最大收益
        profit[0] = profitMap.get(difficulty[0]);
        for (int i = 1; i < n; i++) {
            profit[i] = Math.max(profit[i - 1], profitMap.get(difficulty[i]));
        }
        for (int i = 0; i < m; i++) {
            int index = Arrays.binarySearch(difficulty, worker[i]);
            if (index >= 0) {
                res += profit[index];
            } else {
                index = -index - 2;
                if (index >= 0) {
                    // 说明没有能力完成
                    res += profit[index];
                }
            }
        }
        return res;
    }

    // 参考官网题解的答案
    public static class Point{
        public int x;
        public int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int maxProfitAssignment_v1(int[] difficulty, int[] profit, int[] worker) {
        int res = 0;
        int n = difficulty.length;
        Point[] jobs = new Point[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Point(difficulty[i], profit[i]);
        }
        Arrays.sort(jobs, (a, b) -> a.x - b.x);
        // 根据工人技能排序
        // 越往后能力越高，可以直接接着上一次难度位置向后遍历
        Arrays.sort(worker);
        int index = 0;
        int best = 0;
        for (int capability : worker) {
            while (index < n && capability >= jobs[index].x) {
                best = Math.max(best, jobs[index++].y);
            }
            res += best;
        }
        return res;
    }
}

性能

最后计算最大收益时在循环中使用二分查找，时间复杂度为O(mlogn)，而使用双指针 difficulty 最多遍历一遍，时间复杂度是O(m + n)应该更快一点。另外使用hashMap效率不高，因为需要计算hashcode，不如直接访问。

改进后