Алгоритм для задачи

Question

Я пытаюсь уменьшить сложность этого l oop, вот мой код

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]] ", что является corrent

, но это решение имеет временную сложность ( N ^ 2), это можно сделать в O (N) и O (NLgN)? Для этого предложите алгоритм / код / ​​псевдо-код.

программа в основном сравнивает каждое значение с любым другим значением, суммирует два значения и сравнивает с 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]]

Answer 1

При массив всегда сортируется в порядке убывания, вы можете сделать это путем сканирования массива с обоих концов. Примерно так:

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 становится больше, чем значение, то для числа, на которое указывает p1, нет пары.