跳转至

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

题目描述

在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。

返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望下标数字 i 和 j 满足  i < j 且有 (time[i] + time[j]) % 60 == 0。

 

示例 1：

输入：time = [30,20,150,100,40]
输出：3
解释：这三对的总持续时间可被 60 整除：
(time[0] = 30, time[2] = 150): 总持续时间 180
(time[1] = 20, time[3] = 100): 总持续时间 120
(time[1] = 20, time[4] = 40): 总持续时间 60

示例 2：

输入：time = [60,60,60]
输出：3
解释：所有三对的总持续时间都是 120，可以被 60 整除。

 

提示：

  • 1 <= time.length <= 6 * 104
  • 1 <= time[i] <= 500

解法

方法一：数学 + 计数

如果一个数对 \((a, b)\) 之和能被 \(60\) 整除，即 \((a + b) \bmod 60 = 0\)，那么 \((a \bmod 60 + b \bmod 60) \bmod 60 = 0\)，不妨记 \(x=a \bmod 60\), \(y = b \bmod 60\)，那么有 \((x + y) \bmod 60 = 0\)，即 \(y=(60 - x) \bmod 60\)。

因此，我们可以遍历歌曲列表，用一个长度为 \(60\) 的数组 \(cnt\) 记录每个余数 \(x\) 出现的次数。对于当前的 \(x\)，如果数组 \(cnt\) 中存在余数 \(y = (60 - x) \bmod 60\)，那么将 \(cnt[y]\) 累加进答案中。然后，将 \(x\) 在数组 \(cnt\) 中的出现次数加 \(1\)。继续遍历，直到遍历完整个歌曲列表。

遍历结束后，即可得到满足条件的歌曲对数目。

时间复杂度 \(O(n)\)，空间复杂度 \(O(C)\)。其中 \(n\) 是歌曲列表的长度；而 \(C\) 是余数的可能取值，这里 \(C=60\)。

1
2
3
4
5
6
7
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        cnt = Counter(t % 60 for t in time)
        ans = sum(cnt[x] * cnt[60 - x] for x in range(1, 30))
        ans += cnt[0] * (cnt[0] - 1) // 2
        ans += cnt[30] * (cnt[30] - 1) // 2
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] cnt = new int[60];
        for (int t : time) {
            ++cnt[t % 60];
        }
        int ans = 0;
        for (int x = 1; x < 30; ++x) {
            ans += cnt[x] * cnt[60 - x];
        }
        ans += (long) cnt[0] * (cnt[0] - 1) / 2;
        ans += (long) cnt[30] * (cnt[30] - 1) / 2;
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int cnt[60]{};
        for (int& t : time) {
            ++cnt[t % 60];
        }
        int ans = 0;
        for (int x = 1; x < 30; ++x) {
            ans += cnt[x] * cnt[60 - x];
        }
        ans += 1LL * cnt[0] * (cnt[0] - 1) / 2;
        ans += 1LL * cnt[30] * (cnt[30] - 1) / 2;
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func numPairsDivisibleBy60(time []int) (ans int) {
    cnt := [60]int{}
    for _, t := range time {
        cnt[t%60]++
    }
    for x := 1; x < 30; x++ {
        ans += cnt[x] * cnt[60-x]
    }
    ans += cnt[0] * (cnt[0] - 1) / 2
    ans += cnt[30] * (cnt[30] - 1) / 2
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function numPairsDivisibleBy60(time: number[]): number {
    const cnt: number[] = new Array(60).fill(0);
    for (const t of time) {
        ++cnt[t % 60];
    }
    let ans = 0;
    for (let x = 1; x < 30; ++x) {
        ans += cnt[x] * cnt[60 - x];
    }
    ans += (cnt[0] * (cnt[0] - 1)) / 2;
    ans += (cnt[30] * (cnt[30] - 1)) / 2;
    return ans;
}

方法二

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        cnt = Counter()
        ans = 0
        for x in time:
            x %= 60
            y = (60 - x) % 60
            ans += cnt[y]
            cnt[x] += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] cnt = new int[60];
        int ans = 0;
        for (int x : time) {
            x %= 60;
            int y = (60 - x) % 60;
            ans += cnt[y];
            ++cnt[x];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int cnt[60]{};
        int ans = 0;
        for (int x : time) {
            x %= 60;
            int y = (60 - x) % 60;
            ans += cnt[y];
            ++cnt[x];
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func numPairsDivisibleBy60(time []int) (ans int) {
    cnt := [60]int{}
    for _, x := range time {
        x %= 60
        y := (60 - x) % 60
        ans += cnt[y]
        cnt[x]++
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function numPairsDivisibleBy60(time: number[]): number {
    const cnt: number[] = new Array(60).fill(0);
    let ans: number = 0;
    for (let x of time) {
        x %= 60;
        const y = (60 - x) % 60;
        ans += cnt[y];
        ++cnt[x];
    }
    return ans;
}

评论