Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
如何在 O(n log n) 时间内在未排序的集合 S 中找到两个不同的数字 a 和 b,以便 |ab| 是所有可能的对中最小的吗?
首先,使用快速排序对列表进行排序,即 O(n log n)。
然后对列表进行一次遍历,测量每个数字与下一个数字之间的间隔,并跟踪您看到的最小间隔。那是 O(n)。
O(n) + O(n log n) = O(n log n)