任务的算法

我试图降低这个循环的复杂度,以下是我的代码。

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)中完成?请提出一个算法codepsuedo-code来解决这个问题。

程序基本上是将每个值与其他值进行比较,将两个值相加,然后与x进行比较,如果等于x,则将其追加到一个列表中。

数组总是按降序排序.我们必须找到”[array[i]+array[j]==值,其中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]]

解决方案:

作为 数组总是排序的 按降序排列,你可以通过从两端扫描数组来实现。 类似这样

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所指向的数字就没有对了。

给TA打赏
共{{data.count}}人
人已打赏
解决方案

春季安全 - OPTIONS调用时的403状态响应

2022-5-12 16:00:23

解决方案

如何检查Pandas数据框内的列表是否为空?

2022-5-12 16:00:25

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索