时间戳

首页 > 解决方案 > 为列表中的每个元组查找最接近的元组的算法

algorithm - 为列表中的每个元组查找最接近的元组的算法

问题描述

考虑一个元素数组，其中每个元素都是一对，例如 (a,b) 第一个元素 a 是日期，b 是某个正整数。给定的数组根据日期排序。我们必须编写一个返回整数数组的函数。数组中第 i 个位置的每个元素都派生自原始数组中对应的元组元素，如下所示。

以第 i 个元组说 (a,b) 。现在看看它之后出现的所有元组。并找到一个 (c,d) 使得 d 小于 b 并且是最大值。返回数组中的第 i 个元素将是 (ca)。

我的想法 -
我们从给定元组数组的右侧扫描。每次遇到元组时，我们都会将它添加到 AVL 树
中。现在搜索需要的时间等于树的高度。因此，如果元素不同，这将在 n log n 时间内起作用。但是如果元组中的第二个元素出现的次数更多，那么我们最终可能会遍历整个树。不知道如何解决这个问题。

我们可能可以将 min 和 Max 节点存储在每个子树的节点中。

标签： algorithmavl-tree

解决方案

//input list of pair is of the form (date, value)
//DS is a data structure that support lower bound search and insert in O(logn)

index = size of list of pair - 1
for (pair p in input list of pair, scanning from right to left):

    //search should return a sentinel if DS is empty
    resultant_array[index--] = pair<p.date, search(previous of lower bound of p.value in DS)?.date>

    if(DS doesn't contain pair with key p.value)
        insert in DS the pair <p.value, p.date>

如果 (a, b) 中的 b 可能重复，则上述算法考虑最高日期。要取最低日期，如果 DS 中存在 p.value，则在算法的最后一行更新而不是插入。

DS 可以是有序的 map、AVL、red-black 等。即使在日期重复值的情况下，也不需要遍历整个 DS。因此，每次搜索只需 O(logn)。

推荐阅读