标签： 哈希表

目标

森林中有未知数量的兔子。提问其中若干只兔子 "还有多少只兔子与你（指被提问的兔子）颜色相同?" ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ，返回森林中兔子的最少数量。

示例 1：

输入：answers = [1,1,2]
输出：5
解释：
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。 
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。 
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。 
因此森林中兔子的最少数量是 5 只：3 只回答的和 2 只没有回答的。

示例 2：

输入：answers = [10,10,10]
输出：11

说明：

• 1 <= answers.length <= 1000
• 0 <= answers[i] < 1000

思路

对森林中的兔子提问 有多少只兔子与你颜色相同？answers[i] 表示下标为 i 的兔子的回答，问森林中最少有多少只兔子。

假设被提问的兔子的颜色都不相同，那么兔子最少有 sum(answers[i]) + n，即被提问的兔子个数 n 加上与它们颜色相同的兔子个数。

如果被提问的兔子的颜色相同，那么它们的回答一定相同。可以根据回答进行分组，如果分组个数 groupCnt 超过了颜色个数 colorCnt，说明是其它颜色。只需要分组后对 groupCnt / colorCnt 向上取整，然后乘以 colorCnt 即可，即 ⌈groupCnt / colorCnt⌉ * colorCnt。

代码

/**
 * @date 2025-04-20 14:09
 */
public class NumRabbits781 {

    public int numRabbits(int[] answers) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : answers) {
            map.merge(num, 1, Integer::sum);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer colorCnt = entry.getKey() + 1;
            Integer groupCnt = entry.getValue();
            int colors = (groupCnt + colorCnt - 1) / colorCnt;
            res += colors * colorCnt;
        }
        return res;
    }
}

性能

目标

给你一个下标从 0 开始的整数数组 nums 。如果 i < j 且 j - i != nums[j] - nums[i] ，那么我们称 (i, j) 是一个 坏数对 。

请你返回 nums 中 坏数对 的总数目。

示例 1：

输入：nums = [4,1,3,3]
输出：5
解释：数对 (0, 1) 是坏数对，因为 1 - 0 != 1 - 4 。
数对 (0, 2) 是坏数对，因为 2 - 0 != 3 - 4, 2 != -1 。
数对 (0, 3) 是坏数对，因为 3 - 0 != 3 - 4, 3 != -1 。
数对 (1, 2) 是坏数对，因为 2 - 1 != 3 - 1, 1 != 2 。
数对 (2, 3) 是坏数对，因为 3 - 2 != 3 - 3, 1 != 0 。
总共有 5 个坏数对，所以我们返回 5 。

示例 2：

输入：nums = [1,2,3,4,5]
输出：0
解释：没有坏数对。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

思路

求数组中有多少坏数对，定义坏数对 (i, j) 满足 i < j && j - i != nums[j] - nums[i]。

将题目中的条件转化一下，j - nums[j] != i - nums[i]，可以维护一个 下标 - 元素值 数组。问题变为求当前下标前有多少个元素与当前元素 不同。对元素值计数，使用当前元素下标（表示 i 前的元素个数）减去当前元素值在前面的出现次数即可。

代码

/**
 * @date 2025-04-18 8:52
 */
public class CountBadPairs2364 {

    public long countBadPairs(int[] nums) {
        int n = nums.length;
        long res = 0L;
        Map<Integer, Long> cnt = new HashMap<>();
        for (int i = 0; i < n; i++) {
            res += i - cnt.merge(i - nums[i], 1L, Long::sum) + 1;
        }
        return res;
    }
}

性能

目标

给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组：

• 二维数组应该 只 包含数组 nums 中的元素。
• 二维数组中的每一行都包含 不同 的整数。
• 二维数组的行数应尽可能 少 。

返回结果数组。如果存在多种答案，则返回其中任何一种。

请注意，二维数组的每一行上可以存在不同数量的元素。

示例 1：

输入：nums = [1,3,4,1,2,3,1]
输出：[[1,3,4,2],[1,3],[1]]
解释：根据题目要求可以创建包含以下几行元素的二维数组：
- 1,3,4,2
- 1,3
- 1
nums 中的所有元素都有用到，并且每一行都由不同的整数组成，所以这是一个符合题目要求的答案。
可以证明无法创建少于三行且符合题目要求的二维数组。

示例 2：

输入：nums = [1,2,3,4]
输出：[[4,3,2,1]]
解释：nums 中的所有元素都不同，所以我们可以将其全部保存在二维数组中的第一行。

说明：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= nums.length

思路

将数组转化为二维数组，要求每一行元素没有重复，并且行数尽可能地少。

使用哈希表对相同元素计数，将所有 key 放入一行并将所有 key 的计数减一，如果计数减为 0 则删除 key，直到哈希表为空，时间复杂度为 O(n)。

也可以将哈希表改为数组相当于计数排序。

代码

/**
 * @date 2025-03-19 0:21
 */
public class FindMatrix2610 {

    public List<List<Integer>> findMatrix(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }
        List<List<Integer>> res = new ArrayList<>();
        while (!map.isEmpty()) {
            res.add(new ArrayList<>());
            List<Integer> list = res.get(res.size() - 1);
            Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Integer, Integer> entry = iterator.next();
                list.add(entry.getKey());
                entry.setValue(entry.getValue() - 1);
                if (entry.getValue() == 0) {
                    iterator.remove();
                }
            }
        }
        return res;
    }

}

性能

目标

给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。

整天 定义为时间持续时间是 24 小时的 整数倍 。

例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。

示例 1：

输入： hours = [12,12,30,24,24]
输出： 2
解释：
构成整天的下标对分别是 (0, 1) 和 (3, 4)。

示例 2：

输入： hours = [72,48,24,3]
输出： 3
解释：
构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。

说明：

• 1 <= hours.length <= 5 * 10^5
• 1 <= hours[i] <= 10^9

思路

有一个整数数组 hours，返回 hours[i] + hours[j] % 24 == 0，i < j 的下标对的个数。

与昨天的题目 3184.构成整天的下标对数目I 相比，数据规模从 100 变成了 5 * 10^5。枚举下标对的时间复杂度为 O(C(n,2))，即 O(n^2)，肯定会超时。

题目并不要求输出具体的下标对，只需要计数即可。当枚举右端点时，如果可以直接获取到已访问过的元素中，能够与当前元素组成合法下标对的元素个数，那么整体的时间复杂度可以降为 O(n)。定义 cnt[m] 表示已访问过的元素中对 24 取余后值为 m 的元素个数。当枚举到元素 i 时，只需累加 cnt[24 - nums[i] % 24] 即可。

代码

/**
 * @date 2024-10-23 10:16
 */
public class CountCompleteDayPairs3185 {

    public long countCompleteDayPairs_v2(int[] hours) {
        long res = 0L;
        int[] cnt = new int[24];
        int zeroCnt = 0;
        for (int hour : hours) {
            int m = hour % 24;
            if (m == 0) {
                res += zeroCnt;
                zeroCnt++;
            } else {
                res += cnt[24 - m];
                cnt[m]++;
            }
        }
        return res;
    }

}

性能

目标

给你一个整数数组 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;
    }
}

性能

暴力解

哈希加排序