使用凸包算法对整数进行排序

Question

4

二维凸包的算法使用排序。假设有人给您一个实现凸包的库作为黑匣子。展示如何使用凸包算法对给定整数序列进行排序。黑匣子意味着您不能查看代码，您只知道输入和输出以及结果的样子。您不能从凸包库的实现中“取出排序算法”。您可以将凸包算法视为原始步骤进行调用。请注意，保留HTML标记。

- user1858533

除了凸包程序之外，还允许哪些其他操作？我假设不会比较整数？而凸包程序也不能保证返回的壳点的顺序？ - finnw

2个回答

2

将整数视为位于x轴上的点（即y坐标为零）。将这些点输入凸包算法。如果算法无法处理这种退化情况，请将每个整数转换为两个点（x，1）和（x，-1）。作为算法的输出，您将得到形成封闭回路（多边形）的点。绕一圈并找到x最小的点，之后点的递增x值将表示排序后的整数。

同样，如果凸包算法在处理位于同一直线上的边界点时有问题，则使用y值的平方来强调凸性 - 当然，如果所有整数都是非负的。如果存在负整数，则需要在计算y值的平方之前减去最小值。

- Igor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ícaro Dourado · Accepted Answer

对于输入序列A=[x1,...,xn]中的每个整数xi，n=|A|，创建其对应的点(xi，xi^2)，然后在二维空间中组合n个点。这些点形成一个凸曲线抛物线。您可以在线性时间内检查这些点以检测最左边的点pl，然后从点pl开始遍历凸包到右侧，以产生数字x1，...，xn的排序顺序。

由于Ω(n logn)是基于比较的排序的下限，我们可以认为凸包所需的时间不少于此，否则排序就可以更便宜地完成其下限，这将导致收缩。