java - 搜索值最接近 N 的数组的索引 - Java

Question

任何人都可以提供关于如何在不使用 API 类的情况下在数组中搜索与无序数组中的 N 最接近的值的建议吗？我不希望我的算法是线性时间的。

实现此目的的一种方法是对数组进行排序，然后进行二分搜索？

有更有效的方法吗？

Answer 1

正如 @ThomasPastircak 所写，如果数组未排序，您将不会获得比线性时间性能更好的性能。

将数组中的数据插入到另一个数据结构中至少具有线性复杂度(因为数组的所有元素都需要插入其中)，并且对其进行排序也会比线性复杂度更差。

你的问题和问题“如何在未排序的数组中搜索最大/最小数字？”之间没有太大区别。。您只是在寻找与引用值 N 的最小差异。

一个简单的解决方案是:

public static int closest(double[] array, double n) {
    double leastDifference = Double.POSITIVE_INFINITY;
    int indexOfLeastDifference = -1;
    for (int a = 0; a < array.length; a++) {
        double difference = Math.abs(array[a] - n);
        if (difference < leastDifference) {
            indexOfLeastDifference = a;
            leastDifference = difference;
        }
    }
    return indexOfLeastDifference;
}