python - 考虑一个整数数组 n A=[a1,a2,a3......an]。查找并打印满足 ai*aj <= max(ai,ai+1,.....aj) 的总对数，其中 i < j

Question

谁能帮我解决上面的问题。我们必须在数组 (a1,a2),(a1,a3),(a1,a4).... 等中找到元素的组合，然后选择满足条件 (ai*aj) <= max 的组合(A) 其中 A 是数组并返回可能的组合数。

示例:输入数组 A = [1,1,2,4,2] 并返回 8，因为组合为:(1,1),(1,2),(1,4),(1,2),(1,2),(1,4),(1,2),(2,2)。

使用嵌套 for 循环很容易解决这个问题，但这会非常耗时。(O(n^2))。

朴素算法:

array = [1,1,2,4,2]
result = []
for i in range(len(array)):
   for j in range(len(array)):
       if array[i] * array[j] <= max(array):
           if (array[j],array[i]) not in result:
               result.append((array[i],array[j]))
print(len(result))

遇到这样的问题应该怎么处理？

Answer 1

阅读您的问题描述后，我的理解是您想要找到乘积小于这些对之间范围内的最大元素的对的总数，即 ai*aj <= max(ai,ai+1,…aj) .

Thomas 建议的天真方法很容易理解，但它的时间复杂度仍然是 O(n^2)) .我们可以优化它以将时间复杂度降低到 O(n*log^2n) .让我们详细讨论一下。

首先，从每个索引-i，我们可以找出范围说{l, r}其中 index- i 处的元素将大于或等于 l 中的所有元素至 i , 以及它大于 i + 1 范围内的所有元素至 r .这可以使用 histogram data-structure 的思想在 O(n) 时间复杂度内轻松计算。 .

现在，对于每个索引-i，我们找出这样的范围{l, r} ，如果我们想遍历两个范围之外的最小长度，即 min( i - l, r - i )那么总的来说我们将遍历n*logn整个数组的索引。在遍历小长度范围时，如果我们遇到一些元素，比如 x ，然后我们必须以某种方式找出其他范围内存在多少元素，使得值小于 ai / x .这可以通过 Fenwick Tree data-structure 的离线处理来解决。每个查询的时间复杂度为 O(logn)。因此，我们可以解决上述问题，整体复杂度为 O(n log^2 n)。时间复杂度。