算法相互

Question

在一定距离内比较数字，所以我有一个看起来像

1,708,234 
2,802,532 
11,083,432 
5,098,123 
5,777,111 

我想搞清楚当两个号码彼此在一定距离内的数字阵列（比如1,500,000），所以我可以将它们分组到相同的位置，并且只有一个UI元素代表我正在查看的缩放级别。如何巧妙或有效地做这件事。我想我只是从第一个入口开始，循环遍历所有元素，并且如果一个接近另一个元素，请将这两个元素标记出来并放入某种字典中。这将是我的蛮力方法，但我认为必须有更好的方法。

我在obj-c btw编码，如果这使得或破坏任何设计决策。

Answer 1

我们在这里处理了多少个数字？如果它足够小：

1. 排序号码（通常正数，n）到每个数字
2. 运行，n和比较其大国邻居，N + 1，看它是否是你的范围内。
3. 重复n + 2，n + 3，直到数字不在您的范围内。

你的蛮力法有O（（n/2）^ 2）。这种方法将在平均情况下将其带到O（n + n log（n））或O（n log n）。