- 题目描述:
-
In a list of songs, the
i
-th song has a duration oftime[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 indicesi < 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
题目大意:求数组中有多少个元素两两组合可以被60整除最后返回符合规则的元素对的个数。
- 解题思路
暴力法:
最容易想到的就是一次枚举所有的元素组合查看是否符合规则,如果符合规则则计数加加最后返回计数的结果
需要两次循环时间复杂度为o(n^2)C(n,2).
map映射:
两个数相加能被60整除必须是两个数除以60的余数和为60,用一个map数组存储余数到个数的映射,如map[2]的值为除以60余数为2的数的个数。
map[2]只能与map[58]组合才符合规则,通过for循环遍历所有的元素,假设当前元素的余数为N,当前元素通过组合能构成符合规则的元素对为map[(60-n)]个数,这样会导致同一元素对被计算两次,但是循环由小到大,在n/2前所有后面的数都为0
- 代码:
class Solution: def numPairsDivisibleBy60(self, time: List[int]) -> int: ''' 求所有和能整除60的数,因为能整除60的数为,两个数除以60 余数相加等于60例如5%60等于5,他能与所有余数为55的数组合 整除60,因此需要记录不同的余数的个数: 本题解题的关键是在不同的余数之间索引 ''' residue=[0]*60 length=len(time) ans=0 for i in range(length): t=time[i]%60 ans+=residue[(60-t)%60]#针对特殊情况何为60时,需要将其进行求模运算 residue[t]+=1 return ans