谁能提供关于不使用API类就如何搜索数组中最接近无序数组N的值的任何建议?我不希望我的算法是线性时间。
执行此操作的一种方法是对数组进行排序,然后进行二元搜索吗?
有没有更有效的方法来做到这一点?
正如@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;
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句