blocks|key|4081566|text|当你把这些对看作是二维点的时候，你就可以在一个坐标系中说明这个问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4081567|现在，您希望将每个点对(点)与点上方具有y坐标宽度的区域中的所有点对(点)连接起来。下图中给出了两个示例。以这种方式构建区域可以确保：|4081568|4081569|您认为的点的y坐标是上面所有点中的最小值。|ordered-list-item|4081570|这些点的x坐标之差不大于y坐标。|4081571|4081572|​|4081573|📷|atomic|offset|length|4081574|4081575|现在的问题是，我们如何快速找到该区域中的点。|4081576|对于这些类型的查询，通常使用R-Trees。你可以在O(n+log+n)中构建一棵R-树。查询的复杂性取决于查询的选择性，在这个问题中还取决于数据分布。如果幸运的话，它是O(log+)，但对于每个点，它也可能收敛到O(n)。|4081577|但是，如果我理解正确的话，您并不是对所有的配对都感兴趣，而只是对配对的数量感兴趣。如果是这种情况，您可以向R-Tree页面添加一个计数器，用于存储每个页面中存储的点数。然后，您实际上不必验证所有的点，这可以使您更接近每个点的O(log+)。|4081578|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/e7bee787bd48c0c70cb29c56f0284341.png|imageAlt|1|LINK|MUTABLE|url|https://en.wikipedia.org/wiki/R-tree^0|0|0|0|0|0|0|0|0|1|0|0|0|0|E|7|1|0|0^^$0|@$1|2|3|4|5|6|7|1C|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1D|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|1E|8|@]|9|@]|A|$]]|$1|E|3|F|5|G|7|1F|8|@]|9|@]|A|$]]|$1|H|3|I|5|G|7|1G|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|1H|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|1I|8|@]|9|@]|A|$]]|$1|M|3|N|5|O|7|1J|8|@]|9|@$P|1K|Q|1L|1|1M]]|A|$]]|$1|R|3|L|5|6|7|1N|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|1O|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|1P|8|@]|9|@$P|1Q|Q|1R|1|1S]]|A|$]]|$1|W|3|X|5|6|7|1T|8|@]|9|@]|A|$]]|$1|Y|3|-4|5|6|7|1U|8|@]|9|@]|A|$]]]|Z|$10|$5|11|12|13|A|$14|15|16|-4]]|17|$5|18|12|19|A|$1A|1B]]]]

When you treat the pairs as two dimensional points then you can illustrate the problem in a coordinate system. 

Now you want to join each pair (point) with all pairs (points) that are in the region above the point with a width of the y coordinate of the point. Two examples are given in the image below. Constructing the region in this way ensures that: 

<ol>
<li>the y coordinate of the point you consider is the minimum of all points above.</li>
<li>the difference of the x coordinates of the points is no larger than this y coordinate.</li>
</ol>

<a href="https://i.stack.imgur.com/V48LF.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/V48LF.png" alt="enter image description here"></a>

The question now becomes, how can we quickly find the points in the area.

For these kind of queries <a href="https://en.wikipedia.org/wiki/R-tree" rel="nofollow noreferrer">R-Trees</a> are usually utilized. You can build an R-Tree in O(n log n). The querying complexity depends on the selectivity of your query and in this problem on the data distribution. If you are lucky it is O(log n) but it might also converge to O(n) for each point.

However, if I understand you correct, you are not interested in all the pairs, but only in the number of pairs. If this is the case, you can add a counter to the R-Tree pages storing the number of points that are stored in each page. Then you do not really have to verify all points which can bring you closer to O(log n) per points.

blocks|key|4745002|text|你们的配对是坐标。把它们当做位置。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4745003|对于给定的坐标(x，y)，匹配的坐标形成一个从x轴发射到高度y的圆锥体，然后它变成一个以x为中心的宽度为2y%2B1的列，直到无限大。|4745004|因此，现在您需要一种方法来计算这样一个区域中的元素数量，而无需执行任何按元素计算的工作。|4745005|假设您有一个从(x，y)到该点上方和左侧的点的#的映射(称之为平方累积图)。然后计算列部分需要2次查找和一次减法。应该可以在O(n+lg+n)时间内构建这样的映射。|4745006|可以使用类似的几何累积计数来有效地计算三角形或锥形区域中的元素的计数。例如，如果我们有一个从k到#+of+elements的映射，使用(x-y)>=k，您可以在1次查找中计算三角形中的元素数，然后在平方累加图中查找3次，然后进行2次减法和1次加法。|4745007|有一个相反方向的对角累积图，你现在可以计算上面指定的圆锥体中元素的数量。|4745008|4745009|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|Q|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|R|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|S|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|T|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|N|$]]

Your pairs are coordinates. Treat them as positions.

For a given coordinate (x,y) the coordinates that match form a cone eminating from the x axis until it reaches height y. Then it becomes a column of width 2y+1 centered on x going up to infinity.

So now you need a way to count the elements in such a region without doing any per-element work.

Imagine you had a map from (x,y) to # of points above and left of that point (call this the square accumulation map). Then calculating the column part takes 2 lookups and a subtraction. It should be possible to build such a map in O(n lg n) time or so.

Similar geometrical accumulation counts could be used to efficiently calculate counts of elements in triangular or cone regions. For example, if we had a maps from k to # of elements with (x-y)>=k you can calculate the count of elements in a triangle in 1 lookup there, and 3 lookups into the square accumulation map, followed by 2 subtractions and 1 addition.

Have an opposite direction diagonal accumulation map and you can now calculate count of elements in a cone as specified above.

If lookups take lg(n) time, building these maps takes O(n lg n) time, then we can simply iterate over each point (n of them), calculate the number of nearby points (lg n work), sum it it up, divide by 2 (as we double-counted each one), and we have an O(n lg n) solution to your problem.

blocks|key|4745015|text|让我们按照第二个值以非递增的顺序对我们的对进行排序。然后按此顺序遍历这些对。假设当前对具有索引i，并查看所有对(j,+i)，其中为j+<+i。我们知道这些对中的第二个元素的最小值是pairs[i].second+(因为它的顺序不是递增的)。然后我们需要找出索引的数量j，其中|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|4745016|+%7Cpairs[j].first+-+pairs[i].first%7C+<=+pairs[i].second|code-block|syntax|javascript|4745017|让我们重新制定:我们需要找出索引为j+<+i的对的第一个元素的数量，它们位于区间内：|4745018|[pairs[i].first+-+pairs[i].second,+pairs[i].first+%2B+pairs[i].second]|4745019|例如，可以使用O(log(n))中的augmented+self-balancing+BST+(我们可以保留和更新每个顶点中的子代数量)来实现这一点。伪码：|4745020|res+=+0
sort+pairs+by+second+value+in+non-increasing+order
for+i+=+1+to+n
++++res+%2B=+number+of+elements+in+BST+on+interval+[pairs[i].first+-+pairs[i].second,+pairs[i].first+%2B+pairs[i].second]
++++add+pairs[i].first+to+BST+++|4745021|总体复杂度将是O(n*log(n))。|4745022|如果对中的整数值为O(n)，则可以使用Fenwick+tree或Segment+tree替换BST。|4745023|entityMap|0|LINK|mutability|MUTABLE|url|http://www.bowdoin.edu/~ltoma/teaching/cs231/spring14/Lectures/10-augmentedTrees/augtrees.pdf|1|https://en.wikipedia.org/wiki/Fenwick_tree|2|https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/^0|1B|1|1J|6|1T|5|2I|F|3P|1|0|0|H|5|0|0|7|9|I|S|0|0|0|7|B|0|9|4|J|C|1|W|C|2|0^^$0|@$1|2|3|4|5|6|7|18|8|@$9|19|A|1A|B|C]|$9|1B|A|1C|B|C]|$9|1D|A|1E|B|C]|$9|1F|A|1G|B|C]|$9|1H|A|1I|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|1J|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|1K|8|@$9|1L|A|1M|B|C]]|D|@]|E|$]]|$1|M|3|N|5|H|7|1N|8|@]|D|@]|E|$I|J]]|$1|O|3|P|5|6|7|1O|8|@$9|1P|A|1Q|B|C]]|D|@$9|1R|A|1S|1|1T]]|E|$]]|$1|Q|3|R|5|H|7|1U|8|@]|D|@]|E|$I|J]]|$1|S|3|T|5|6|7|1V|8|@$9|1W|A|1X|B|C]]|D|@]|E|$]]|$1|U|3|V|5|6|7|1Y|8|@$9|1Z|A|20|B|C]]|D|@$9|21|A|22|1|23]|$9|24|A|25|1|26]]|E|$]]|$1|W|3|-4|5|6|7|27|8|@]|D|@]|E|$]]]|X|$Y|$5|Z|10|11|E|$12|13]]|14|$5|Z|10|11|E|$12|15]]|16|$5|Z|10|11|E|$12|17]]]]

Let's sort our pairs by second values in non-increasing order. Then iterate through the pairs in this order. Assume that current pair has index <code>i</code>, and look at all pairs <code>(j, i)</code>, where <code>j &lt; i</code>. We know that minimum of the second elements of these pairs is <code>pairs[i].second</code> (because of the non-increasing order). Then we need to find the number of indices <code>j</code> where

<pre><code> |pairs[j].first - pairs[i].first| &lt;= pairs[i].second
</code></pre>

Let's reformulate: we need to find the number of first elements of pairs with indices <code>j &lt; i</code> that are lying inside the interval: 

<pre><code>[pairs[i].first - pairs[i].second, pairs[i].first + pairs[i].second]
</code></pre>

This can be done, for example, with <a href="http://www.bowdoin.edu/~ltoma/teaching/cs231/spring14/Lectures/10-augmentedTrees/augtrees.pdf" rel="nofollow noreferrer">augmented self-balancing BST</a> (we can keep and update the number of children in each vertex) in <code>O(log(n))</code>. 
Pseudocode: 

<pre><code>res = 0
sort pairs by second value in non-increasing order
for i = 1 to n
 res += number of elements in BST on interval [pairs[i].first - pairs[i].second, pairs[i].first + pairs[i].second]
 add pairs[i].first to BST 
</code></pre>

Overall complexity will be <code>O(n*log(n))</code>.

If integer values in the pairs are <code>O(n)</code>, BST can be replaced, for example, with <a href="https://en.wikipedia.org/wiki/Fenwick_tree" rel="nofollow noreferrer">Fenwick tree</a> or a <a href="https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/" rel="nofollow noreferrer">Segment tree</a>.

Given an array of integer pairs <code>pair&lt;int,int&gt;</code>, it is required to find number of pairs of <code>pair&lt;&gt;</code> such that the absolute difference between the first elements of the pairs is less than or equal to the minimum of the second elements of the pairs. 

Eg: 

<pre><code>Pair 1: 2,5
Pair 2: 7,4
Since (7-2) &lt;= min(5,4) it is a valid pair
</code></pre>

PS: I was expecting a better time complexity than the naive <code>O(N*N)</code>.

Number of pairs of pairs with difference between first elements less than or equal to minimum of the second elements

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

给定整数对pair<int,int>的阵列，需要找出pair<>对的数目，使得对的第一元素之间的绝对差小于或等于对的第二元素的最小值。例如：Pair 1: 2,5Pair 2: 7,4Since (7-2) <= min(5,4) it is a valid pairPS:我期待着比朴素的O(N*N)更好的时间复杂度。

问第一元素之间的差小于或等于第二元素中的最小值的对的数量
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问第一元素之间的差小于或等于第二元素中的最小值的对的数量EN