12

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

4

5 回答 5

8

这是一个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 问题所做的事情。

*这里的“选择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)。

于 2013-11-07T16:39:46.920 回答
1

这是一个二进制搜索，O(n log n)：

处的每个数字都有一个断点A*B = A+B。您可以将其减少到B = A / (A - 1). 一侧或另一侧的所有数字都适合它。是否有负数等都没关系。

  • 如果A < 1，则所有数字都<= B适合。

  • 如果A > 1，则所有数字都>= B适合。

  • 如果A == 1，则不匹配（除以零）。

（Wolfram Alpha 链接）

所以一些伪代码：

loop through i
    a = A[i]
    if(a == 1)
        continue
    if(a >= 2)
        count += A.length - i 
        continue

    j = binsearch(a / (a-1))

    if(j <= i)
        continue

    if(a < 1)
        count += j-i
    if(a > 1)
        count += A.length - j
于 2013-11-07T17:01:07.237 回答
1

您可以在O(n log n).

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

使用二进制搜索找到 A[j] >= k 的最低j值是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) 好。

于 2013-11-07T16:03:44.310 回答
1

O(n)当数组的元素为正时，这是一个解决问题的算法。

当元素为正时，我们可以说：

  • 如果A[i]*A[j] >= A[i]+A[j]什么时候j>i满足A[k]*A[j] >= A[k]+A[j]任何条件k（k>i因为数组已排序）。

  • 如果什么A[i]*A[j] < A[i]+A[j]时候满足的j>i话。A[i]*A[k] < A[i]+A[k]kk<j

（当两个数字都是分数时，这些事实不成立，但无论如何都不会满足条件）

因此我们可以执行以下算法：

int findNumOfPairs(float A[])
{    
    start = 0;
    end = A.length - 1;
    numOfPairs = 0;

    while (start != end)
    {
        if (A[start]*A[end] >= A[start]+A[end])
        {
            numOfPairs += end - start;
            end--;
        }
        else
        {
            start++;
        }
    }

    return numOfPairs;
}
于 2013-11-07T16:16:00.543 回答
-1

首先排除所有小于 1.0 的浮点数怎么样，因为任何数小于 1 的倍数，每个 i < j 的 x*0.3=A[i]+A[j]，所以我们只需要计算数组的数量要计算pairs（i，j）的数量，我们可以使用关于排列组合的公式来计算它。公式应为 n(n-1)/2。

于 2013-11-07T16:21:51.643 回答