[Swift]LeetCode1010. 总持续时间可被 60 整除的歌曲 | Pairs of Songs With Total Durations Divisible by 60
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10546217.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
In a list of songs, the i-th song has a duration of time[i] seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0.
Example 1:
Input: [30,20,150,100,40] Output: 3 Explanation: Three pairs have a total duration divisible by 60: (time[0] = 30, time[2] = 150): total duration 180 (time[1] = 20, time[3] = 100): total duration 120 (time[1] = 20, time[4] = 40): total duration 60
Example 2:
Input: [60,60,60] Output: 3 Explanation: All three pairs have a total duration of 120, which is divisible by 60.
Note:
1 <= time.length <= 600001 <= time[i] <= 500
在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望索引的数字 i < j 且有 (time[i] + time[j]) % 60 == 0。
示例 1：
输入：[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：
输入：[60,60,60] 输出：3 解释：所有三对的总持续时间都是 120，可以被 60 整数。
提示：
1 <= time.length <= 600001 <= time[i] <= 500
212ms
1 class Solution {
2 func numPairsDivisibleBy60(_ time: [Int]) -> Int {
3 var res = 0
4 var rems: [Int] = Array(repeating: 0, count: 60)
5 for t in time {
6 rems[t % 60] += 1
7 }
8 for i in (0..<rems.count - 1) {
9 for j in (i..<rems.count) {
10 if (i + j) % 60 == 0 {
11 if i == j {
12 res = res + ((rems[i] * (rems[i] - 1)) / 2)
13 } else if rems[i] != 0 && rems[j] != 0 {
14 res += (rems[i] * rems[j])
15 }
16 }
17 }
18 }
19 return res
20 }
21 }228ms
1 class Solution {
2 func numPairsDivisibleBy60(_ time: [Int]) -> Int {
3 if time.count <= 1 { return 0 }
4 let count = time.count
5 var rs = [Int](repeating: 0, count: count)
6 var map = [Int: Int]()
7 var pair = 0
8 for i in 0..<count {
9 let r = time[i] % 60
10 if let c = map[r] {
11 map[r] = c + 1
12 } else {
13 map[r] = 1
14 }
15 }
16 for i in 1..<30 {
17 guard let c1 = map[i], let c2 = map[60 - i] else { continue }
18 pair += c1 * c2
19 }
20 if let c = map[0], c > 1 {
21 pair += (c * (c - 1)) / 2
22 }
23 if let c = map[30], c > 1 {
24 pair += (c * (c - 1)) / 2
25 }
26 return pair
27 }
28 }Runtime: 232 ms
Memory Usage: 19.4 MB
1 class Solution {
2 func numPairsDivisibleBy60(_ time: [Int]) -> Int {
3 var n:Int = time.count
4 var cnt:[Int] = [Int](repeating:0,count:60)
5 var ans:Int = 0
6 for i in 0..<n
7 {
8 var t:Int = time[i] % 60
9 ans += cnt[(60 - t) % 60]
10 cnt[time[i] % 60] += 1
11 }
12 return ans
13
14 }
15 }236ms
1 class Solution {
2 func numPairsDivisibleBy60(_ time: [Int]) -> Int {
3 if time.count == 0 {
4 return 0
5 }
6
7 var tempDic = [Int : Int]()
8
9 for temp in time {
10 let v = temp % 60
11 let number = tempDic[v] ?? 0
12 tempDic[v] = number + 1
13 }
14
15 var total = 0
16
17 for (key, value) in tempDic {
18
19 if key == 30 || key == 0 {
20 if value > 1 {
21 let temp = value * (value - 1) / 2
22 total += temp
23 }
24 }
25 else {
26 let v1 = 60 - key
27 if let cache = tempDic[v1] {
28 total += value * cache
29 tempDic[v1] = nil
30 }
31 }
32 tempDic[key] = nil
33 }
34 return total
35 }
36 }252ms
1 class Solution {
2 func numPairsDivisibleBy60(_ time: [Int]) -> Int {
3 var bucket = Array(repeating: 0, count: 60)
4
5 for time in time {
6 bucket[time % 60] += 1
7 }
8
9 var result = 0
10 for i in 1...29 {
11 result += bucket[i] * bucket[60 - i]
12 }
13
14 if bucket[0] >= 2 {
15 result += bucket[0] * (bucket[0] - 1) / 2
16 }
17 if bucket[30] >= 2 {
18 result += bucket[30] * (bucket[30] - 1) / 2
19 }
20
21 return result
22 }
23 }256ms
1 class Solution {
2 func numPairsDivisibleBy60(_ time: [Int]) -> Int {
3 var res = 0
4 var val = [Int: Int]()
5
6 for t in time {
7 let a = t % 60
8 let sup = (60 - a) % 60
9 res += val[a, default: 0]
10 if let v = val[sup] {
11 val[sup] = v + 1
12 } else {
13 val[sup] = 1
14 }
15 }
16 return res
17 }
18 }