Блог

Если у меня есть массив, который отсортирован по первому элементу: [(2021/01/01, 100), (2021/01/02, 5320), …, (2021/01/07, 23)], как мне вывести массив таким образом, чтобы каждый элемент содержал количество дней между днями от входного кортежа t до будущегодата во входном массиве, имеющая наименьшую положительную разницу между числом в кортеже t и числом в будущем кортеже даты.

Например, [(2021/01/01, 100), (2021/01/02, 5320), (2021/01/04, 5319), (2021/01/09, 23)] есть решение:

[8, 2, 5, 0]

Пояснение: Для первого числа 100 и 23 ближе всего, а 9 — 1 = 8.

Моя попытка:

 for i from 0 to n-1:
    m = inf
    for j from 1 to n:
        if a[i].value >= a[j].value and a[i].value - a[j].value < m:
               m = a[i].value - a[j].value
               update the current min date difference
    add to list of min date differences

return that list
 

Я написал n^2 алгоритм, но я пытаюсь сделать его более эффективным. Я предполагаю, что я могу превратить это в двоичное дерево, но мне не везет. Если бы кто-нибудь мог направлять меня, я был бы вам очень признателен!

Вы можете просмотреть входные данные в обратном порядке и построить сбалансированное дерево поиска (например, AVL, red-black, B-tree, …) из уже посещенных значений, упорядоченных по числовой части кортежей.

Значения в сбалансированном дереве поиска могут быть найдены за O (logn) времени, а учитывая (путь к) узлу, последующие и предшествующие узлы могут быть найдены за O (1) среднее время.

Итак, найдите узел-предшественник и узел-преемник в этом дереве на основе текущего посещаемого значения. Любой из этих двух будет представлять минимальную разницу с текущим числом и, таким образом, выводит соответствующую разницу в день в списке результатов с текущим индексом.

Вот некоторый псевдокод, в котором я предполагаю, что уже существует реализация сбалансированного дерева поиска. Это сбалансированное дерево поиска должно быть способно принимать функцию сравнения, чтобы оно знало, как сравнивать два узла, add метод next и previous методы на своих узлах (интерфейсы могут отличаться):

 function compare(x, y):  # two elements from the input array
    if x.value === y.value:  # equal? then prefer the earliest date:
        return x.date - y.date  # assuming this returns a signed number of days
    else:  
        return x.value - y.value

function getResult(a):
    tree = AVL(compare)  # keeps order by using the given compare function
    result = array(len(a))  # array of same length as a
    for i from n-1 downto 0:
        days = infinity
        node = tree.add(a[i])  # create an AVL node, insert it in the tree and return it
        successor = node.next()  # can return NIL when there is no successor
        if successor != NIL:
            days = abs(successor.date - node.date)
        predecessor = node.previous()
        if predecessor != NIL:
            days = min(days, abs(predecessor.date - node.date)
        result[i] = days

    result[n-1] = 0  # Optional, when you prefer 0 there instead of infinity
    return result