我得到一个不一定排序的整数数组。我必须找到一对 nos,其彼此之间的差异与数组中任何其他对 nos 中的任何一个相比最小。时间效率应该是O(n)。
最佳答案
我很确定您无法针对此问题获得通用的线性时间算法!
但是,由于您有(有界的)整数,您可以稍微作弊并开始使用基数排序对数组进行排序,这是线性时间!然后找到最近的相邻对,这又是线性的。
关于c - 一种 O(n) 时间复杂度的算法,用于在数组中找到彼此之间差异最接近的一对 nos,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4990060/