最近，我正在尝试以下问题：
Given an array of integers, arr.
Find sum of floor of (arr[i]/arr[j]) for all pairs of indices (i,j).
例如
Input: arr[]={1,2,3,4,5}
Output: Sum=27.
说明：
(1/1)+(1/5)+(1/4)+(1/2)+(1/3) = 1+0+0+0+0 = 1
(5/1)+(5/5)+(5/4)+(5/2)+(5/3) = 5+1+1+2+1 = 10
(4/1)+(4/5)+(4/4)+(4/2)+(4/3) = 4+0+1+2+1 = 8
(2/1)+(2/5)+(2/4)+(2/2)+(2/3) = 2+0+0+1+0 = 3
(3/1)+(3/5)+(3/4)+(3/2)+(3/3) = 3+0+0+1+1 = 5
我只能想到天真的O（n ^ 2）解决方案。还有其他更好的方法吗？
提前致谢。
一种可能性是“快速”跳过与给定元素相同整数倍的元素（四舍五入后）。
对于给定的示例，下面的竖线以相等的比率定界游程（下部三角形全为零，被忽略；我在左边显示元素，在右边显示比率）：
1 -> 2 | 3 | 4 | 5 ≡ 2 | 3 | 4 | 5
2 -> 3 | 4 5 ≡ 1 | 2 2
3 -> 4 5 ≡ 1 1
4 -> 5 ≡ 1
对于更大的数组，恒定运行时间可能更长。
所以算法原理是
逐步对所有要素进行分类；
从最小到最大处理元素；
一项关键操作是“找到下一个倍数”。这应该通过指数搜索后再进行二分搜索来完成，这样操作的数量就可以跳过的元素数量保持对数（纯二分搜索将成为剩余元素总数的对数）。因此，搜索成本将与倍数之间距离的对数之和成正比。
希望该总和小于距离本身的总和，尽管在最坏的情况下复杂度仍然存在O(N)。在最佳情况下，O(log(N))。
全局分析是困难的，理论上最坏的情况仍然存在O(N²)；但实际上，它可以归结为O(N log N)，因为最坏的情况将要求元素的生长速度快于共同比率2的几何级数。
附录：
如果数组包含大量重复值，则可以通过存储重复计数和每个值的单个实例来压缩它。可以在排序后完成。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句