时间戳

首页 > 解决方案 > 任务算法

python - 任务算法

问题描述

我正在尝试降低此循环的复杂性，这是我的代码

def find_indexes(array, size, value):
    list_indexes = []
    for i in range(size):
        for j in range(size):
            if (array[i] + array[j] == value and i != j):
                list_indexes.append([i, j])
    return list_indexes

array = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
find_indexes(array, len(array), 12)

输出显示“[[0, 8], [1, 7], [2, 6], [3, 5], [5, 3], [6, 2], [7, 1], [8, 0]]" 这是正确的

但是这个解决方案有时间复杂度 (N^2)，这可以在 O(N) 和 O(NLgN) 中完成吗？请为此提出一个算法/代码/伪代码。

该程序基本上将每个值与每个其他值进行比较，将两个值相加并与 x 进行比较。如果它等于 x。它将它附加到一个列表中。

数组始终按降序排序。我们必须找到“[array[i] + array[j] == value，其中 i 和 j 是数组的两个独立索引]”

O(N) 中的解决方案

import math
array = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
size = len(array)
X = 12

def Q1_1_N(array, size, value):
    list_indexes = []

    i, j = 0, size - 1
    while (i <= j):
        j = size - 1
        while(j != int((size / 2) - 1)):
            if array[i] + array[j] == value:
                list_indexes.append([i, j])
            j -= 1
        i += 1

    return list_indexes


result = Q1_1_N(array, size, X)
print("Array :", array, "\nX :", X)
if result == []:
    print([-1, -1])
else:
    print("Result Indexes :", result)

输出 ：

数组：[10、9、8、7、6、5、4、3、2、1]

X : 12

结果索引：[[0, 8], [1, 7], [2, 6], [3, 5]]

标签： pythonalgorithmanalysis

解决方案

由于数组始终按降序排序，您可以通过从两端扫描数组来做到这一点。像这样的东西

p1 = 0
p2 = array.size -1
while p1 < p2
   let v = array[p1] + array[p2]
   while v < value
      if v = value then
          result.append(p1,p2)
          break -- exit the while loop
       p2--
       let v = array[p1] + array[p2]
   p1++

当指针与您完成后一样，您将生成已找到的配对的镜像。

如果 v 变得大于 value，则 p1 指向的数字不存在一对。

推荐阅读