查找最接近的数字在无序数组 [英] Find nearest number in unordered array

问题描述

鉴于大量无序排列长随机数和目标长，什么是最有效的算法寻找最接​​近的号码吗？

  @Test
公共无效findNearest（）抛出异常{
    最终长[]号= {90L，10L，30L，50L，70L};
    Assert.assertEquals（最近，10L，findNearest（数字，12L））;
}
 

解决方案

通过多头的数组迭代一次。存储当前最接近号码和该数字的距离。继续检查每一个数字，如果它是更接近，只是取代目前最接近的数字，当你遇到一个更近一些。

这让你的O（n）的最佳性能。

建立一个二叉树所建议的其他回答者将O（nlogn）。当然，未来的搜索将只需要O（LOGN）......所以，如果你做了很多搜索它可能是值得的。

如果你是职业球员，你可以使用OpenMP或线程库并行这一点，但我猜那是你的问题的范围。

Given a large unordered array of long random numbers and a target long, what's the most efficient algorithm for finding the closest number?

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

解决方案

Iterate through the array of longs once. Store the current closest number and the distance to that number. Continue checking each number if it is closer, and just replace the current closest number when you encounter a closer number.

This gets you best performance of O(n).

Building a binary tree as suggested by other answerer will take O(nlogn). Of course future search will only take O(logn)...so it may be worth it if you do a lot of searches.

If you are pro, you can parallelize this with openmp or thread library, but I am guessing that is out of the scope of your question.

这篇关于查找最接近的数字在无序数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！