algorithm - 查找乘积大于总和的对

Question

给定一个排序的 float 组作为输入，我需要找到对的总数 (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 之间的对，我做了类似于 the 3SUM problem 的操作。 .

* 这里的“选2”是指combinations .

• 计算所有都是负数的对

  进行二进制搜索以找到第一个正数 (> 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) .