-4

如何在 O(n log n) 时间内在未排序的集合 S 中找到两个不同的数字 a 和 b,以便 |ab| 是所有可能的对中最小的吗?

4

1 回答 1

1

首先,使用快速排序对列表进行排序,即 O(n log n)。

然后对列表进行一次遍历,测量每个数字与下一个数字之间的间隔,并跟踪您看到的最小间隔。那是 O(n)。

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

于 2013-03-29T04:02:29.180 回答