总持续时间可被 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个槽来存储模数结果,而不是使用其它数字或数据结构?
▷🦆
为什么在计算模数0和30的配对数时采用了组合数公式,这种计算方式在什么情况下是正确的?
▷🦆
算法中提到了对于模数1到29及其与60的补数进行配对,为什么没有包括模数30以上的数字?
▷