给定一个未排序的整数数组，并且不对数组中的数字做任何假设：Is it possible to find two numbers whose difference is minimum in O(n) time?
Edit: 两个数字a，b之间的差异定义为 abs(a-b)
abs(a-b)
查找列表中的最小和最大元素 . 最小的差异将是最小的 .
如果你正在寻找非负差异，那么这当然至少和检查数组是否有两个相同元素一样困难 . 这被称为element uniqueness problem并且没有任何其他假设（如限制整数的大小，允许除比较之外的其他操作）需要> = n log n时间 . 这是找到closest pair of points的一维情况 .
使用radixsort（对于整数为O（n））对列表进行排序，然后迭代并跟踪到目前为止的最小距离 .
（我假设你的整数是一个固定位类型 . 如果它们可以容纳任意大的数学整数，那么radixsort也将是O（n log n） . ）
它可以在O（n * sqrt（log（log（n）））时间内对无界的整数组进行排序 . 在排序之后，找到线性时间的最小差异当然是微不足道的 .
但我想不出任何算法让它比这更快 .
不，不是没有对数字/排序做出假设 .
虽然可以给出一个排序列表 .
我不认为你能在O（n）中做到这一点 . 我能想到的最好的是对它们进行排序（即O（n * log n））并找到排序列表中相邻对的最小差异（这会增加另一个O（n）） .
我认为这是可能的 . 秘诀是你实际上不必对列表进行排序，你只需要创建一个存在数字的计数 . 从算法的角度来看，这可能算作“做出假设”，但不是从实际的角度来看 . 我们知道整数由最小值和最大值限制 .
因此，创建一个包含2位元素的数组，每个int的1对从INT_MIN到INT_MAX（含），将它们全部设置为00 .
遍历整个数字列表 . 对于列表中的每个数字，如果相应的2位为00，则将它们设置为01.如果它们是01，则将它们设置为10.否则忽略 . 这显然是O（n） .
接下来，如果2位中的任何一位设置为10，那么这就是你的答案 . 最小距离为0，因为列表包含重复的数字 . 如果没有，请扫描列表并找到最小距离 . 很多人已经指出有简单的O（n）算法 .
所以O（n）O（n）= O（n） .
编辑：回复评论 .
有趣的一点 . 我认为你可以通过首先找到列表的最小值/最大值并使用从最小值到最大值的稀疏数组来保存数据而不做任何假设就可以获得相同的结果 . 考虑INT_MIN / MAX假设，空间复杂度和扫描阵列的O（m）时间复杂度 .
我认为答案是否定的，证明类似于你不能比n lg n更快排序的证明：你必须比较所有元素，即创建一个比较树，这意味着omega（n lg n）算法 .
EDIT . 好的，如果你真的想争论，那么问题就不是说它应该是图灵机了 . 使用量子计算机，你可以在线性时间:)
我能想到的最好的是counting sort数组（可能组合相等的值）然后进行排序比较 - bin排序是O（n M）（M是不同值的数量） . 然而，这需要大量内存 . 某种形式的桶或基数排序在时间上是中间的并且在空间上更有效 .
8 回答
查找列表中的最小和最大元素 . 最小的差异将是最小的 .
如果你正在寻找非负差异，那么这当然至少和检查数组是否有两个相同元素一样困难 . 这被称为element uniqueness problem并且没有任何其他假设（如限制整数的大小，允许除比较之外的其他操作）需要> = n log n时间 . 这是找到closest pair of points的一维情况 .
使用radixsort（对于整数为O（n））对列表进行排序，然后迭代并跟踪到目前为止的最小距离 .
（我假设你的整数是一个固定位类型 . 如果它们可以容纳任意大的数学整数，那么radixsort也将是O（n log n） . ）
它可以在O（n * sqrt（log（log（n）））时间内对无界的整数组进行排序 . 在排序之后，找到线性时间的最小差异当然是微不足道的 .
但我想不出任何算法让它比这更快 .
不，不是没有对数字/排序做出假设 .
虽然可以给出一个排序列表 .
我不认为你能在O（n）中做到这一点 . 我能想到的最好的是对它们进行排序（即O（n * log n））并找到排序列表中相邻对的最小差异（这会增加另一个O（n）） .
我认为这是可能的 . 秘诀是你实际上不必对列表进行排序，你只需要创建一个存在数字的计数 . 从算法的角度来看，这可能算作“做出假设”，但不是从实际的角度来看 . 我们知道整数由最小值和最大值限制 .
因此，创建一个包含2位元素的数组，每个int的1对从INT_MIN到INT_MAX（含），将它们全部设置为00 .
遍历整个数字列表 . 对于列表中的每个数字，如果相应的2位为00，则将它们设置为01.如果它们是01，则将它们设置为10.否则忽略 . 这显然是O（n） .
接下来，如果2位中的任何一位设置为10，那么这就是你的答案 . 最小距离为0，因为列表包含重复的数字 . 如果没有，请扫描列表并找到最小距离 . 很多人已经指出有简单的O（n）算法 .
所以O（n）O（n）= O（n） .
编辑：回复评论 .
有趣的一点 . 我认为你可以通过首先找到列表的最小值/最大值并使用从最小值到最大值的稀疏数组来保存数据而不做任何假设就可以获得相同的结果 . 考虑INT_MIN / MAX假设，空间复杂度和扫描阵列的O（m）时间复杂度 .
我认为答案是否定的，证明类似于你不能比n lg n更快排序的证明：你必须比较所有元素，即创建一个比较树，这意味着omega（n lg n）算法 .
EDIT . 好的，如果你真的想争论，那么问题就不是说它应该是图灵机了 . 使用量子计算机，你可以在线性时间:)
我能想到的最好的是counting sort数组（可能组合相等的值）然后进行排序比较 - bin排序是O（n M）（M是不同值的数量） . 然而，这需要大量内存 . 某种形式的桶或基数排序在时间上是中间的并且在空间上更有效 .