例如如果数组 A 是
A[0] = 0.1
A[1] = 0.6
A[2] = 1.2
A[3] = 1.7
A[4] = 3.5
然后对于 (3,4) 对，我们有 A[3]*A[4] > A[3]+A[4]
我想找出数组中此类对的数量。
还有 A[i] = A1[i] + A2[i]/1,000,000
其中 A1 和 A2 是给定的输入，A1 和 A2 已排序。
用 O(n^2) 算法回答是微不足道的。有人告诉我有 O(n) 解决方案，无需使用额外空间。我正在寻找那个。
最佳答案
x * y > x + y
除以 x*y(对于正值)
1/x + 1/y < 1
让我们第一个光标(R)指向右边的元素(最小 1/a[i] 值)，第二个光标(L)指向左边的元素。
将L向右移动，直到倒数和为1。
将 (R-L) 添加到结果。
向左走 R 步。
重复移动L，直到R和L相遇
两个游标最多移动 N 步，所以算法需要 O(N)
关于java - 查找数组中的对数，其中 A[i] * A[j] > A[i] + A[j]，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24802091/