Обход только тех элементов, которые делятся текущим элементом в массиве

Question

Рассмотрим массив: 10 2 4 14 1 7 Обходя входной массив для каждого допустимого i, я должен найти все элементы, которые делятся на i-й элемент. Итак, сначала я должен найти все элементы, которые больше, чем i-й элемент.

Пример вывода:

10 -> null
2 -> 10
4 -> 10
14 -> null
1 -> 14,4,2,10
7 -> 14,10

Мой подход: я думал о создании двоичного дерева, котороебудет выполнять операцию log n для каждой допустимой вставки в массив, которая будет перестраивать двоичное дерево с минимальным элементом в качестве корневого элемента, меньшим элементом слева и большим элементом справа. Теперь мне нужно пройти через правое поддерево вставленного элемента и проверить, какие элементы делятся на i-й элемент. Это очень дорогой подход, но лучше, чем грубая сила.

Может ли кто-нибудь помочь найти оптимальное решение, которое было бы более эффективным?

Answer 1

построил список убывающих прогонов

Поскольку список сканируется, если текущий элемент <= элемент в конце последнего прогона, добавьте его в прогон. Это не так, начать новый прогон с текущим элементом. </p>

Пример массива становится [[10, 2], [4], [14, 1], [7]].

Теперь достаточно просто просканировать каждый прогон и сделать что-то с элементами, которыебольше чем элемент [i].

Вот пример кода, который обрабатывает входной массив и возвращает список списков.

def bigger_so_far(seq):
    results = []
    runs = []

    for element in seq:
        if runs:
            if element > runs[-1][-1]:
                runs.append([])
            runs[-1].append(element)

        else:
            runs.append([element])

        result = []
        for run in runs:
            for j in run:
                if j <= element:
                    break
                result.append(j)

        results.append(result)

    print(runs)

    return results

Пример выполнения:

bigger_so_far([10, 2, 4, 14, 1, 7]) #=> [[], [10], [10], [], [10, 2, 4, 14], [10, 14]]

Answer 2

Сложность времени не может быть лучше, чем O (n ^ 2). Следовательно, решение грубой силы просто отлично.

Рассмотрим приведенный ниже ввод (который также является наихудшим):

arr = [1, 1, 1,  ..., 1, 1]

Для arr[0] = 1, в ответе,будет 0 elements.

Для arr[1] = 1, в ответе будет 1 element.

...

Для arr[n - 2] = 1, вв ответе будет n - 2 elements.

Для arr[n - 1] = 1 в ответе будет n - 1 elements.

Итак, общее количество элементов в ответе не будет:

0 + 1 + 2 + ... + (n - 1)
= ((n - 1) * n) / 2
= O(n^2)

Если вы просто хотите найти the number of elements and not the actual elements, то да, есть лучшие решения.