平均找到差值小于 K 且复杂度为 O(n) 的配对
Find Pair with Difference less than K with O(n) complexity on average
我有一个未排序的n正数数组和一个参数k，我需要找出数组中是否有一对数字之间的差值小于k 并且我需要在 O(n) 的时间复杂度和 O(n) 的 space 复杂度中这样做。
我认为它需要使用通用哈希 table 但我不确定如何使用，有什么想法吗？
简单的解决方案：
1- 对数组进行排序
2-计算连续元素的差值
a) 如果差值小于k return 那对
b) 如果没有连续的数差产生小于k的值，那么你的数组中没有一对数差小于k。
排序是O(nlogn)，但是如果你只有有限大小的整数，你可以使用计数排序，即O(n)
可以这样考虑
问题可以这样建模：-
考虑每个元素（考虑整数），现在将它们转换为一个范围 (A[i]-K,A[i]+K)
现在您想检查两个区间是否重叠。
没有任何排序的区间交叉问题在O(n)（最坏情况）中无法解决。你需要对它们进行排序，然后 inn O(n) 你可以检查它们是否相交。
你的逻辑也是一样。排序并找到它。
这个答案甚至适用于无界整数和浮点数（对您将使用的哈希图的准确性做一些假设 - 例如 java 实现应该有效）：
保持一个hashmap<int, float> all_divided_values。对于每个键 y，
如果 all_divided_values[y] 存在，它将包含一个值 v
在数组中使得 floor(v/k) = y.
对于原始数组A中的每个值v，如果v/k在all_divided_values的键中，则输出(v, all_divided_values[v/k])
（它们之间的距离小于 k）。否则，将 v 存储在
all_divided_values[v/k]
填满all_divided_values后，再次通过A。对于每个 v，测试 all_divided_values[v/k - 1] 是否存在，如果存在，
当且仅当 abs(v-all_divided_values[v/k - 1])<=k
(v, all_divided_values[v/k - 1])
在hashmap中插入通常（以Java hashmap为例）平均O(1)，所以总时间是O(n)。但请注意，从技术上讲这可能是错误的，例如，如果您的语言的实现没有关于哈希图的良好策略。
我有一个未排序的n正数数组和一个参数k，我需要找出数组中是否有一对数字之间的差值小于k 并且我需要在 O(n) 的时间复杂度和 O(n) 的 space 复杂度中这样做。
我认为它需要使用通用哈希 table 但我不确定如何使用，有什么想法吗？
简单的解决方案：
1- 对数组进行排序
2-计算连续元素的差值
a) 如果差值小于k return 那对
b) 如果没有连续的数差产生小于k的值，那么你的数组中没有一对数差小于k。
排序是O(nlogn)，但是如果你只有有限大小的整数，你可以使用计数排序，即O(n)
可以这样考虑
问题可以这样建模：-
考虑每个元素（考虑整数），现在将它们转换为一个范围 (A[i]-K,A[i]+K)
现在您想检查两个区间是否重叠。
没有任何排序的区间交叉问题在O(n)（最坏情况）中无法解决。你需要对它们进行排序，然后 inn O(n) 你可以检查它们是否相交。
你的逻辑也是一样。排序并找到它。
这个答案甚至适用于无界整数和浮点数（对您将使用的哈希图的准确性做一些假设 - 例如 java 实现应该有效）：
保持一个
hashmap<int, float> all_divided_values。对于每个键y， 如果all_divided_values[y]存在，它将包含一个值v在数组中使得floor(v/k) = y.对于原始数组
A中的每个值v，如果v/k在all_divided_values的键中，则输出(v, all_divided_values[v/k])（它们之间的距离小于 k）。否则，将v存储在all_divided_values[v/k]填满
all_divided_values后，再次通过A。对于每个v，测试all_divided_values[v/k - 1]是否存在，如果存在， 当且仅当abs(v-all_divided_values[v/k - 1])<=k 时输出对
(v, all_divided_values[v/k - 1])
在hashmap中插入通常（以Java hashmap为例）平均O(1)，所以总时间是O(n)。但请注意，从技术上讲这可能是错误的，例如，如果您的语言的实现没有关于哈希图的良好策略。