猿问

有效地计算给定总和的所有对

我遇到了以下问题。

给定一个列表,其中每个项目表示以秒为单位表示的歌曲持续时间,返回歌曲对的总数,例如它们的持续时间总和为分钟(例如,1m0s、2m0s、..)

示例:
输入:[10,50,20,110,40]
输出:3(考虑索引 (0,1),(0,3),(2,4) 处的对)

我只能想到一种蛮力的方法,我会考虑所有对的歌曲。这种方法的时间复杂度是 O(n^2)。
有没有更好的方法来做到这一点?


慕田峪4524236
浏览 171回答 2
2回答

肥皂起泡泡

给定的问题可以简化为这样一个事实,即我们需要从给定的列表 A 中发现(a,b)这样的对(a + b) mod 60 == 0。观察 #1:对于任何整数 x,(x mod 60) 位于 o 到 59 之间。初始化一个长度为 60 的数组,默认值设置为 0,其索引i将存储列表 A 中元素的数量,这样x mod 60 = i对于属于 A 的所有 xint freq[60] = {0};for(int i = 0; i < A.size(); i++)&nbsp; freq[(A[i] % 60)]++;现在再次迭代数组 A,对于每个 x,我们需要60 - (x mod 60)累积频率图中索引的计数,这将对应于它可以与之形成对的元素的数量。情况 where(x mod 60) == 30将是一个棘手的问题,这将要求我们从频率计数中减去 1。int ans = 0;for(int i = 0; i < A.size(); i++) {&nbsp; ans += freq[60 - (A[i] % 60)];&nbsp; if(A[i] % 60 == 30) ans--;}解决方案的整体复杂度为 O(n)。

炎炎设计

想想散列、创建桶和模除法。所有可能的分钟将进入 60 个可能的桶之一。然后想想当您从任意两个存储桶中选择两个第二个值时,可以有多少种可能的组合。然后用 nC2 计数。这是我在 Java 中的解决方案。public int numPairsDivisibleBy60(int[] time) {&nbsp; &nbsp; int k = 60;&nbsp; &nbsp; int[] mods = new int[k];&nbsp; &nbsp; for (int i = 0; i < time.length; i++)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; mods[time[i] % k]++;&nbsp; &nbsp; // n(n-1)/2 pairs for multiples of k and numbers which leave remainder as half multiple of k&nbsp; &nbsp; int count = ((mods[0] * (mods[0] - 1)) / 2) +&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ((mods[k / 2] * (mods[k / 2] - 1)) / 2);&nbsp; &nbsp; for (int i = 1; i < k / 2; i++)&nbsp; &nbsp; &nbsp; &nbsp; count += mods[i] * mods[k - i];&nbsp; &nbsp; return count;}
随时随地看视频慕课网APP

相关分类

Java
我要回答