根据 O(N) 中的面积对矩形进行排序 [英] Sort rectangles according to area in O(N)

问题描述

令 R1,...Rn 是平面中的 n 个轴对齐矩形，其角是 n×n 网格中的点.因此，对于每个矩形 Ri，四个角是两个坐标都是 {1,...n} 中的整数的点.

Let R1,...Rn be n axis-aligned rectangles in the plane for which the corners are points in the n×n-grid. Thus, for each rectangle Ri the four corners are points where both coordinates are integers in {1,...n}.

现在我想通过 O(n) 时间内增加的面积对这些矩形 R1,...Rn 进行排序.

Now I want to sort these rectangles R1,...Rn by there increasing area in O(n) time.

我有一个算法可以在 O(n*log n) 中对它们进行排序.但是如何在 O(n) 中完成?

I have an algorithm to sort them in O(n*log n). But how can it be done in O(n) ?

使用 O(n*log n) 我们可以做到这一点:

Using O(n*log n) we can do this :

Calculate all the areas, and then sort using any standard sorting algorithm like Quick sort

我想需要一些 per-processing，以便我们可以在 O(n) 中排序，因为我们得到了一些可以提供帮助的先决条件.我只想要算法，不需要代码.

I guess some per-processing will be required, so that we can sort in O(n) , because we are given some pre-conditions which can help. I just want algorithm, no code required.

推荐答案

由于矩形的键(面积)是整数，所以任务可以在 O(n) 时间内使用 O(n) 完成a href="https://en.wikipedia.org/wiki/Counting_sort#The_algorithm" rel="nofollow">计数排序.你知道问题的最小键是 0，最大键是 n^2，所以在算法 k=n^2+1 中.该算法分三步完成:计算直方图，计算每个键的起始和结束索引，然后将数据复制到输出数组，保留具有相等键的输入顺序，以便排序为 稳定.每次传递都是O(n)，所以整个算法是O(n).

Since the keys (areas) of the rectangles are integers, the task can be completed in O(n) time using a counting sort. You know the minimum key is 0 and maximum key for the problem is n^2, so in the algorithm k=n^2+1. The algorithm completes in three passes: computing histogram, computing starting and ending indexes for each key, then copying the data to the output array, preserving order of inputs with equal keys so that the sort is stable. Each pass is O(n) so altogether the algorithm is O(n).

示例:假设 n 为 3.k 比数据中出现的最大键多 1，因此所有键都适合在 [0..k-1] 范围内，即 k 为 10.您使通过设置索引从 0 到 k-1 的 0 数组来绘制直方图 h，然后通过遍历矩形集来填充直方图，然后对它们进行计数.假设有 2 个区域为 1，5 个区域为区域 2，2 个区域为区域 4. h = [0, 2, 5, 0, 2, 0, 0, 0, 0, 0].然后从直方图中立即计算起始索引为 0, 0, 2, 7, 7, 9, 9, 9, 9, 9.任何面积为 0 的矩形进入从 0 开始的输出数组.任何面积为 1 的矩形进入进入从 0 开始的输出数组(并在将区域 1 的矩形放入输出时增加该数字).任何面积为 2 的矩形从 2 开始进入输出数组.任何面积为 3 的矩形都从 7 开始进入输出数组.任何面积为 4 的矩形都从 7 开始进入输出数组.

Example: Suppose n is 3. k is one more than the largest key that appears in the data, so that all keys fit in the range [0..k-1] inclusive, i.e., k is 10. You make a histogram h by setting up an array of 0s with index from 0 to k-1, and you fill the histogram by walking through your set of rectangles and just count them up. Say there are 2 with area 1, 5 with area 2, and 2 with area 4. h = [0, 2, 5, 0, 2, 0, 0, 0, 0, 0]. Then the starting indexes are immediately computed from the histogram as 0, 0, 2, 7, 7, 9, 9, 9, 9, 9. Any rectangle with area 0 goes into output array starting at 0. Any rectangle with area 1 goes into output array starting at 0 (and increment that number when you put a rectangle of area 1 into output). Any rectangle with area 2 goes into output array starting at 2. Any rectangle with area 3 goes into output array starting at 7. Any rectangle with area 4 goes into output array starting at 7.

这篇关于根据 O(N) 中的面积对矩形进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！