时间戳

首页 > 解决方案 > 两个元组之间的最低正差

algorithm - 两个元组之间的最低正差

问题描述

如果我有一个按第一个元素排序的数组：[(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算法，但我正在努力提高它的效率。我的猜测是我可以把它变成一棵二叉树，但我没有运气。如果有人可以指导我，我将不胜感激！

标签： algorithm

解决方案

您可以以相反的顺序访问输入，并从已访问的值中构建平衡的搜索树（例如 AVL、红黑、B 树……），按元组的数字部分排序。

平衡搜索树中的值可以在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

推荐阅读