时间戳

首页 > 解决方案 > 考虑一个由整数 A=[a1,a2,a3......an] 组成的数组 n。查找并打印满足 ai*aj <= max(ai,ai+1,.....aj) 其中 i < j 的对的总数

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

问题描述

谁能帮我解决上述问题。我们必须在数组 (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))

当我们遇到此类问题时应该采取什么方法？

标签： pythonalgorithmdata-structures

解决方案

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

因为where i < j我们可以把它减半：

for i in range(len(array)):
  for j in range(i+1, len(array)):
    ...

现在让我们摆脱这部分if (array[j],array[i]) not in result:，因为它不能反映您的结果：(1,1),(1,2),(1,4),(1,2),(1,2),(1,4),(1,2),(2,2)这里有骗子。

我们可以摆脱的下一个昂贵的步骤max(array)不仅是错误的（max(ai,ai+1,…aj)转换为max(array[i:j])），而且必须在每次迭代中迭代整个数组部分。由于 Array 没有改变，唯一可能改变这个最大值的是array[j]你正在处理的新值。

让我们将其存储在一个变量中：

array = [1,1,2,4,2]
result = []

for i in range(len(array)):
  maxValue = array[i]
  for j in range(i+1, len(array)):
    if array[j] > maxValue:
      maxValue = array[j]
    if array[i] * array[j] <= maxValue:
      result.append((array[i], array[j]))

print(len(result))

仍然是一个幼稚的算法，但我们已经做出了一些改进。

我们可以做的另一件事是不仅存储maxValuea ，还存储 a pivot = maxValue / array[i]，因此通过简单的比较来替换乘法if array[j] <= pivot:。这样做是在假设乘法比 the 更频繁地调用的情况下maxValue，因此会更频繁地调用pivot更改。

但是由于我在 python 方面不是很有经验，我不确定这是否会对 python 产生任何影响，或者我是否正在为此进行毫无意义的微优化。

推荐阅读