找到产品大于总和的对

Question

作为输入,浮标的排序后的数组,我需要找到对的总数(i,j)如A[i]*A[j]>=A[i]+A[j]对于每个i < j.我已经知道了天真的解决方案,在其他循环中使用循环,这将给我O(n ^ 2)算法,但我想知道是否有更优化的解决方案.

Answer 1

这是一个O(n)算法.

我们来看看吧A * B >= A + B.

• 什么时候A, B <= 0,它总是如此.

• 什么时候A, B >= 2,它总是如此.

• 当A >= 1, B <= 1(或B >= 1, A <= 1),它总是错误的.

• 何时0 < A < 1, B < 0(或0 < B < 1, A < 0),它可以是真或假.

• 何时1 < A < 2, B > 0(或1 < B < 2, A > 0),它可以是真或假.

这是一个可视化,由Wolfram Alpha和Geobits提供:

现在,进入算法.

*要找到一个数字介于0和1或1和2之间的对,我会做类似于3SUM问题的操作.

*"Pick 2"在这里指的是组合.

• 计算两者都为负数的所有对

  进行二分查找以找到第一个正数(> 0)的索引 - O(log n).

  由于我们有索引,我们知道有多少数是负数/零,我们只需要选择其中的2个,这样就是amountNonPositive * (amountNonPositive-1) / 2- O(1).

• 找到一个介于0和1之间的所有对

  进行二分查找以找到最后一个数字的索引<1 - O(log n).

  从该索引开始作为右索引,最左边的元素作为左索引.

  重复此操作,直到右侧索引<= 0 :(运行O(n))

  • 虽然产品小于总和,但减少左指数

  • 计算大于左索引的所有元素

  • 减少正确的指数

• 找到1到2之间的所有对

  进行二分查找以查找第一个数字的索引> 1 - O(log n).

  从该索引开始,作为左索引,最右边的元素作为右索引.

  重复此操作,直到左侧索引> = 2 :(运行O(n))

  • 虽然产品大于总和,但减少正确的指数

  • 计算大于右索引的所有元素

  • 增加左侧索引

• 计算两个数字> = 2的所有对

  在最后一步结束时,我们处于第一个索引> = 2.

  现在,从那里,我们只需要选择所有剩余数字中的2个,
  所以它再次amountGreaterEqual2 * (amountGreaterEqual2-1) / 2- O(1).

Answer 2

您可以在 中找到并打印这些对（以速记形式）O(n log n)。

对于每个A[i]都有一个k满足条件（1）的最小数量。所有大于 k 的值也将满足条件。

j使用二分查找找到 A[j] >= k 的最低值是O(log n)。

所以你可以找到并打印结果，如下所示：

(i, j)
(1, no match)
(2, no match)
(3, >=25)
(4, >=20)
(5, >=12)
(6, >6)
(7, >7)
...
(n-1, n)       

如果要打印所有组合，那么就是O(n^2)，因为组合的数量是O(n^2)。

(*) 要处理负数，实际上需要更复杂一点，因为满足方程的数字可能不止一个范围。我不确定它对于小负数的表现如何，但如果范围的数量不是绝对有限的，那么我的解决方案不再比 O(n^2) 更好。