You are given a list of songs where the ith 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
such that i < j
with (time[i] + time[j]) % 60 == 0
.
Example 1:
Input: time = [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: time = [60,60,60] Output: 3 Explanation: All three pairs have a total duration of 120, which is divisible by 60.
题目是需要求数组中,一对数字对,满足二者之和能被60整除。这道题很容易可以写出暴力求解的版本。
class Solution { public: int numPairsDivisibleBy60(vector<int>& time) { // 暴力法 int n=time.size(); int res=0; for(int i=0;i<n;++i){ for(int j=i+1;j<n;++j){ if((time[i]+time[j])%60==0) res++; } } return res; } };
再数字较多的情况下就会超时,那么该如何优化呢? 暴力法的之间复杂是o(n*n), 这时候再回过头看题目的要求,(time[i]+time[j])%==0 <=>time[i]%60+time[j]%60==0, 此时有两种情况满足上述要求,要么两个数字time[i],time[j]都能被60整除,要么其余数加和等于60,这个时候用一个mark数组记录当前余数的个数,并同时更新结果就好了。这种解法时间复杂度为o(n),可以说非常的高效了。
感觉这种优化思路非常有意思。
class Solution { public: int numPairsDivisibleBy60(vector<int>& time) { // 暴力法 int res=0; int mark[60]={0}; for(int i=0;i<time.size();++i){ int a=time[i]%60; if(a==0){ res+=mark[0]; //查看之前该种余数的个数 } else{ res+=mark[60-a]; } mark[a]++; //要之后更新 } return res; } };