leetcode
leetcode 901 ~ 950
总持续时间可被 60 整除的歌曲

总持续时间可被 60 整除的歌曲

难度:

标签:

题目描述

代码结果

运行时间: 36 ms, 内存: 20.4 MB


/*
 * 题目思路:
 * 使用Java Stream的方式可以更简洁地实现上述逻辑。
 * 我们依旧利用余数进行配对,使用Collectors和Stream的特性来实现。
 */
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        Map<Integer, Long> remaindersCount = IntStream.of(time)
            .mapToObj(t -> t % 60)
            .collect(Collectors.groupingBy(r -> r, Collectors.counting()));
        
        return remaindersCount.entrySet().stream()
            .mapToInt(entry -> {
                int remainder = entry.getKey();
                long count = entry.getValue();
                if (remainder == 0 || remainder == 30) {
                    return (int) (count * (count - 1) / 2);
                } else if (remainder < 30) {
                    long complementCount = remaindersCount.getOrDefault(60 - remainder, 0L);
                    return (int) (count * complementCount);
                } else {
                    return 0;
                }
            })
            .sum();
    }
}

解释

方法:

题解使用了哈希表来统计每个时间模60的结果的频率。接着,对于每种模数结果,寻找与其配对的模数结果,使得两者之和为60。特别地,对于模数0和30的情况(即自身加自身能被60整除的情况),使用组合数公式计算配对方式。这种方法避免了直接的双层循环暴力检查,从而提高了效率。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在哈希表中为什么选择使用60个槽来存储模数结果,而不是使用其它数字或数据结构?
选择使用60个槽来存储模数结果是因为题目要求找出两首歌的总持续时间可以被60整除。通过计算每首歌持续时间对60的余数(模数),我们可以简化问题为查找两个数的模数之和是否等于60。哈希表(或字典)以余数作为键,以该余数出现的次数作为值,非常适合于快速查找和更新操作。使用60个槽正好覆盖了所有可能的余数结果(0到59),这是因为任何数除以60的余数必定在这个范围内,因此这样的数据结构和大小选择是最合适的。
🦆
为什么在计算模数0和30的配对数时采用了组合数公式,这种计算方式在什么情况下是正确的?
在计算模数0和30的配对数时使用组合数公式是因为这两个特殊的模数与自身配对仍然能保持总和被60整除(0+0=0,30+30=60)。组合数公式 C(n, 2) = n*(n-1)/2 是用来计算从n个相同项中任选两项的组合方式的数量。这种计算方式在模数相同且至少出现两次时是正确的,因为每对组合都是一个有效配对。例如,如果某个模数出现了3次,那么这三项之间可以形成3*(3-1)/2 = 3种配对方式。
🦆
算法中提到了对于模数1到29及其与60的补数进行配对,为什么没有包括模数30以上的数字?
算法中对于模数1到29及其与60的补数进行配对,没有包括模数30以上的数字是因为这些情况在计算模数1到29时已经考虑过了。由于模数和其补数的和必须为60,模数1的补数是59,模数2的补数是58,依此类推。当我们考虑到模数29(其补数是31)时,已经包含了所有可能的组合情况,除了模数30(与自身配对),这种情况单独处理。因此,模数30到59的配对在前面已经被算过一次,无需重复计算。

相关问题