【力扣每日一题】解答分析 1010. 总持续时间可被 60 整除的歌曲对数

1010. 总持续时间可被 60 整除的歌曲对数

题目简介

给定一个整数数组 time，表示每首歌曲的持续时间（以秒为单位），我们希望计算出数组中所有歌曲对 (i, j)，使得 i < j 且满足 (time[i] + time[j]) % 60 == 0。换句话说，找出所有的歌曲对，使得它们的播放时间之和能够被 60 整除。

题目要求

• 找出所有歌曲对 (i, j)，使得它们的播放时间之和被 60 整除。
• 解决方案应该能处理 time.length 最大为 6 * 10^4 的情况，因此我们需要优化暴力算法。

暴力解法

暴力解法是直接遍历所有可能的 (i, j) 对，检查它们的总持续时间是否能被 60 整除。虽然这种方法直观且简单，但它的时间复杂度是 O(n^2)，在数据量较大的情况下会超时，无法满足题目对时间效率的要求。

暴力解法代码

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        res = 0
        n = len(time)
        for i in range(n):
            for j in range(i + 1, n):
                if (time[i] + time[j]) % 60 == 0:
                    res += 1
        return res

问题与瓶颈

• 由于暴力解法需要两层循环来遍历所有可能的 (i, j) 对，时间复杂度为 O(n^2)，对于输入大小达到 6 * 10^4 时，可能导致超时。

• 对于 n 较大的输入，暴力算法会执行大约 ( \left(6 \times 10^4 \right)^2 ) 次运算，显然不符合时间要求。

优化思路

我们可以通过 余数配对 的方式来优化该算法，使用一个大小为 60 的数组来统计每个余数出现的次数。具体优化过程如下：

1. 利用余数的特性

对于任意一对歌曲，假设它们的播放时间分别为 t1 和 t2。我们希望 t1 + t2 能被 60 整除，即 (t1 + t2) % 60 == 0。这意味着：

• 如果 t1 % 60 = r1，那么 t2 % 60 = (60 - r1) % 60，才能使得两者的和能被 60 整除。

• 因此，我们可以通过记录每个余数出现的次数，快速找到哪些余数的组合能使得和为 60 的倍数。

2. 优化步骤

• 遍历 time 数组中的每个元素，计算其余数 t % 60。
• 对于每个余数 t % 60 = r，我们要找到与其配对的余数 (60 - r) % 60，并累加已经出现过的配对次数。
• 使用一个大小为 60 的数组 yu_count 来记录每个余数的出现次数。

这样，算法的时间复杂度就降低为 O(n)，大大提高了效率。

优化后的代码

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        yu_count = [0] * 60  # 用来记录余数出现的次数
        res = 0
        
        for x in time:
            t = x % 60  # 计算当前时间的余数
            target = 60 - t if t != 0 else 0  # 计算与当前余数 t 配对的余数
            res += yu_count[target]  # 如果存在这样的余数，累加配对数量
            yu_count[t] += 1  # 更新当前余数的出现次数
        
        return res

代码解释

1. yu_count 数组：

   • yu_count[i] 表示余数为 i 的歌曲出现的次数。该数组的大小为 60，因为余数的范围是 0 到 59。

2. 遍历 time 数组：

   • 对于每个歌曲的播放时间 x，计算它的余数 t = x % 60。
   • 然后找出需要与当前余数配对的目标余数 target = 60 - t（对于 t == 0，目标余数是 0），并累加已经出现的配对数量。
   • 更新当前余数 t 的出现次数。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是歌曲数。我们只遍历一遍 time 数组，每次更新和查询都是常数时间操作。

• 空间复杂度：O(1)，因为 yu_count 数组的大小是固定的 60。

测试案例

示例 1：

输入：

time = [30, 20, 150, 100, 40]

输出：

3

解释：

• (30 + 150) % 60 == 0
• (20 + 40) % 60 == 0
• (100 + 20) % 60 == 0

示例 2：

输入：

time = [60, 60, 60]

输出：

3

解释：

• (60 + 60) % 60 == 0
• (60 + 60) % 60 == 0
• (60 + 60) % 60 == 0

示例 3：

输入：

time = [10, 50, 20, 40, 30]

输出：

3

解释：

• (10 + 50) % 60 == 0
• (20 + 40) % 60 == 0
• (30 + 30) % 60 == 0

错误与改进对比

错误的暴力解法：

暴力解法的时间复杂度是 O(n^2)，对于 n 较大的情况下，可能会导致超时错误，尤其当 n 接近 6 * 10^4 时。

优化后的解法：

优化后的解法通过哈希表统计余数的出现次数，将时间复杂度降低到 O(n)，并且能够在题目给定的时间限制内正确处理大规模数据。

总结

• 通过优化余数的配对计算，利用哈希表存储余数出现次数，将暴力解法的时间复杂度从 O(n^2) 降低到了 O(n)。
• 优化后的解法不仅简洁高效，还能处理大规模数据输入，符合题目的性能要求。