找到两个不同的号码一组为O（n log n）的时间，使他们的差异是最小的所有对

本文介绍了找到两个不同的号码一组为O（n log n）的时间，使他们的差异是最小的所有对的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如何找到两个不同的号码A和B为O一排序的集合S（N log n）的时间，使| AB |是所有可能的对中最小的？

How do I find two distinct numbers a and b in a unsorted set S in O(n log n) time so that |a-b| is the smallest among all possible pairs?

推荐答案

首先，排序列表中使用，比如说，快速排序，这是O（n log n）的。

First, sort the list using, say, quicksort, which is O(n log n).

然后做一个单次通过列表，测量每个数字和之后的数字，并跟踪你所见过的最小间隔时间之间的间隔。这是为O（n）。

Then do a single pass through the list, measuring the interval between each number and the following number, and keeping track of the smallest interval you've seen. That's O(n).

为O（n）+ O（N日志N）=为O（n log n）的

O(n) + O(n log n) = O(n log n)