在无序数组中找到最近的数

Question

给定一个大的无序数组，其中包含许多随机的long数字和一个目标long，寻找最接近目标数字的最有效算法是什么？

@Test
public void findNearest() throws Exception {
    final long[] numbers = {90L, 10L, 30L, 50L, 70L};
    Assert.assertEquals("nearest", 10L, findNearest(numbers, 12L));
}

- Paul McKenzie

---

如何先复制数组，然后对副本进行排序，最后找到最接近的元素呢？ - Swadq

你的意思是最接近的，最大的较小值还是最小的较大值？ - Savino Sguera

@SavinoSguera 最接近的方式。 - Paul McKenzie

Answer 1

遍历long类型数组一次。存储当前最接近的数字和距离该数字的距离。继续检查每个数字是否更接近，并在遇到更接近的数字时替换当前最接近的数字。

这样可以获得O(n)的最佳性能。

按照其他答案建议构建二叉树将需要O(nlogn)的时间。当然，未来的搜索只需要O(logn)……所以如果您进行大量搜索，这可能是值得的。

如果您是专业人士，您可以使用openmp或线程库并行化此过程，但我猜这超出了您的问题范围。

- James Cotter

---

对数组进行排序也会得到相同的O(n log n)进行排序和O(log n)查找最近值的时间复杂度，但会更具内存效率（可能也更快）。 - Peter Lawrey

同意，由于数据局部性，排序会更快。 - James Cotter

@JamesCotter，请详细说明并行化实现。 - Paul McKenzie

Answer 2

如果您不打算在数组上进行多个此类请求，则没有比每个数字的暴力线性时间检查更好的方法。

如果您将在同一数组上执行多个请求，请先对其进行排序，然后在其中执行二进制搜索-这将将此类请求的时间减少到O（log（n）），但您仍需支付O（n * log（n））进行排序，因此只有当请求的数量相当大时才合理，即k * n >>（比n * log（n）+ k * log（n）大得多）。其中k是请求的数量。

如果数组将发生更改，则创建{{link1：二叉搜索树}}并对其进行下限请求。这再次仅在最近的数字请求相对于数组更改请求和元素数量而言相对较大时才合理。由于构建树的成本为O（n * log（n）），更新它的成本也为O（logn），因此您需要具有k * log（n）+ n * log（n）+ k * log（n）<<（远小于）k * n。

- Ivaylo Strandjev

Answer 3

在我看来，我认为你应该使用一个 二叉堆（http://en.wikipedia.org/wiki/Binary_heap），它的插入时间为O(log n)，整个数组的时间复杂度为O(n log n)。对我来说，二叉堆最酷的事情是它可以在自己的数组内部构建，没有额外的开销。看一下heapfy section。

将你的数组进行“堆化”可以在O(1)的时间内获取最大/最小元素。

- Pih

Answer 4

这项工作的时间复杂度是O(n)，其中n为数字的长度。

    final long[] numbers = {90L, 10L, 30L, 50L, 70L};
    long tofind = 12L;
    long delta = Long.MAX_VALUE;
    int index = -1;
    int i = 0;
    while(i < numbers.length){
        Long tmp = Math.abs(tofind - numbers[i]);
        if(tmp < delta){
            delta = tmp;
            index = i;
        }
        i++;
    }

    System.out.println(numbers[index]); //if index is not -1

但是，如果你想在同一个数字数组中查找多次不同的值，比如12L，那么你可以先对数组进行排序，然后在排序后的数字数组上进行二分查找。

- Kleenestar

Answer 5

如果您从数字构建二叉搜索树并进行搜索，则最坏情况下的复杂度为O(log n)。在您的情况下，您不会搜索相等，而是通过减法寻找最小返回值。

- Erhan Bagdemir

Answer 6

我会在遍历数组时检查数字之间的差异，并保存该差异的最小值。

如果您计划多次使用findNearest，我建议在每次更改数组中的值后使用复杂度为n*log(n)的排序算法计算差异。

- dbow

Answer 7

如果你的搜索只需要进行一次，那么你可以像快速排序一样对数组进行划分，使用输入值作为枢轴。

如果在划分时跟踪右半部分中的最小项和左半部分中的最大项，则应该可以在O(n)和对数组的1次遍历中完成。

我认为不可能比O(n)更快，因为它没有排序，你必须至少扫描输入。

如果您需要执行多个后续搜索，则BST确实可以帮助。

- Savino Sguera

Answer 8

您可以按照以下步骤完成此操作：

步骤1：对数组进行排序

步骤2：查找搜索元素的索引

步骤3：根据索引，显示右侧和左侧的数字

如有任何疑问，请告知...

- Fahim Parkar