查找间隔中绝对差最小的两个元素 [英] Find two elements with smallest absolute difference in an interval

问题描述

我得到了一个数组和一个LR类型的查询列表，这意味着找到任何两个数组元素之间的最小绝对差，使得它们的索引介于L和R之间（此处数组的起始索引为1）在0处）

I'm given an array and a list of queries of type L R which mean find the smallest absolute difference between any two array elements such that their indices are between L and R inclusive (Here the starting index of array is at 1 instead of at 0)

例如，使用元素为2 1 8 5 11的数组a，然后查询1-3将为（2 1 8），答案将是1 = 2-1，或查询2-4（1 8 5），答案将是3 = 8-5

For example take the array a with elements 2 1 8 5 11 then the query 1-3 which would be (2 1 8) the answer would be 1=2-1, or the query 2-4 (1 8 5) where the answer would be 3=8-5

现在，如果您必须看一个间隔，对间隔进行排序，然后将第i个元素与第i + 1个元素进行比较，并存储每个i的最小差。

Now this is easy if you have to look at one interval you sort the interval and then compare i-th element with i+1-th and store the minimum difference for each i.

问题是

我要做的是我从第一个数组开始创建了一个带有索引的新数组b一个使得i [= j的a [b [i]]≤a [b [j]]。现在，对于每个查询，我遍历整个数组，查看b [j]是否在L和R之间，如果将它的绝对差值与第一个也是L和R之间的下一个元素进行比较，则保持最小值，然后对

What I've done is I constructed a new array b with indices from the first one such that a[b[i]] <= a[b[j]] for i <= j. Now for each query I loop through the whole array and look if b[j] is between L and R if it is compare its absolute difference to the first next element that is also between L and R keep the minimum and then do the same for that element until you get to the end.

这是低效率的，因为对于每个查询，我都必须检查数组的所有元素，尤其是如果查询的大小小于其大小时的数组。我正在寻找一种省时的方法。

This is inefficient because for each query I have to check all elements of the array especially if the query is small compared to the size of array. I'm looking for a time efficient approach.

编辑：数字不必是连续的，也许我给出了一个错误的数组例如，我的意思是，如果它是1 5 2，那么最小的差就是1 = 2-1。在排序数组中，保证最小的差异肯定在两个连续的元素之间，这就是为什么我想到了排序

The numbers don't have to be consecutive, perhaps I gave a bad array as an example, What I've meant for example if it's 1 5 2 then the smallest difference is 1=2-1. In a sorted array the smallest difference is guaranteed to be between two consecutive elements, that's why I've thought of sorting

推荐答案

I可以画出 O（n（√n）log n）时间解决方案，这可能足够快？当我放弃运动编程时，计算机要慢得多。

I'll sketch an O(n (√n) log n)-time solution, which might be fast enough? When I gave up sport programming, computers were a lot slower.

高级想法是通过以下操作将Mo的技巧应用于数据结构。

The high-level idea is to apply Mo's trick to a data structure with the following operations.

insert(x) - inserts x into the underlying multiset
delete(x) - deletes one copy of x from the underlying multiset
min-abs-diff() - returns the minimum absolute difference
                 between two elements of the multiset
                 (0 if some element has multiplicity >1)

读取所有查询间隔 [l，r] ，对它们进行排序按字典顺序递减的（floor（l / sqrt（n）），r）的顺序，其中 n 是输入，然后处理区间 I ，将元素插入 I-I'，其中 I'是上一个时间间隔，删除 I'-I 中的元素，并报告最小绝对差。 （有趣的排序顺序的目的是将操作数从 O（n ^ 2）减少到 O（n√n）假设 n 个查询。）

Read in all of the query intervals [l, r], sort them in order of lexicographically nondecreasing (floor(l / sqrt(n)), r) where n is the length of the input, and then to process an interval I, insert the elements in I - I' where I' was the previous interval, delete the elements in I' - I, and report the minimum absolute difference. (The point of the funny sort order is to reduce the number of operations from O(n^2) to O(n √n) assuming n queries.)

有两种方法可以实现数据结构 O（log n）时间操作。为了说明的清楚，我将使用二进制搜索树，但是您也可以对数组进行排序并使用分段树（如果您没有允许您指定修饰的BST实现，则工作量会减少）。

There are a couple ways to implement the data structure to have O(log n)-time operations. I'm going to use a binary search tree for clarity of exposition, but you could also sort the array and use a segment tree (less work if you don't have a BST implementation that lets you specify decorations).

向每个BST节点添加三个字段： min （在以该节点为根的子树中的最小值）， max （在此节点处生根的子树中的最大值）， min-abs-diff （在以下位置生根的子树中的值之间的最小绝对差）此节点）。这些字段可以像这样自下而上计算。

Add three fields to each BST node: min (minimum value in the subtree rooted at this node), max (maximum value in the subtree rooted at this node), min-abs-diff (minimum absolute difference between values in the subtree rooted at this node). These fields can be computed bottom-up like so.

if node v has left child u and right child w:
    v.min = u.min
    v.max = w.max
    v.min-abs-diff = min(u.min-abs-diff, v.value - u.max,
                         w.min - v.value, w.min-abs-diff)

if node v has left child u and no right child:
    v.min = u.min
    v.max = v.value
    v.min-abs-diff = min(u.min-abs-diff, v.value - u.max)

if node v has no left child and right child w:
    v.min = v.value
    v.max = w.max
    v.min-abs-diff = min(w.min - v.value, w.min-abs-diff)

if node v has no left child and no right child:
    v.min = v.value
    v.max = v.value
    v.min-abs-diff = ∞

此逻辑可以

if v has a left child u:
    v.min = u.min
    v.min-abs-diff = min(u.min-abs-diff, v.value - u.max)
else:
    v.min = v.value
    v.min-abs-diff = ∞
if v has a right child w:
    v.max = w.max
    v.min-abs-diff = min(v.min-abs-diff, w.min - v.value, w.min-abs-diff)
else:
    v.max = v.value

插入和 delete 照常工作，只是装饰需要沿遍历路径进行更新。对于合理的容器选择，总时间仍为 O（log n）。

insert and delete work as usual, except that the decorations need to be updated along the traversal path. The total time is still O(log n) for reasonable container choices.

min -abs-diff 是通过返回 root.min-abs-diff 实现的，其中 root 是树的根。

min-abs-diff is implemented by returning root.min-abs-diff where root is the root of the tree.

这篇关于查找间隔中绝对差最小的两个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！