我有一个从- 1000到+ 1000的数我有一个数组,里面都是数字。是这样的:
[2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
我想让我得到的数字变成数组中最接近的数字。
例如,我的数字是80,我希望它是82。
我有一个从- 1000到+ 1000的数我有一个数组,里面都是数字。是这样的:
[2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
我想让我得到的数字变成数组中最接近的数字。
例如,我的数字是80,我希望它是82。
当前回答
如果数组像你的例子中那样排序,你可以使用二进制搜索来获得O(log n)更好的时间复杂度。
const myArray = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; const binaryClosestIdx = (arr, target) => { let start = 0; let end = arr.length - 1; let mid = Math.floor((start + end) / 2); while (1) { if (arr[mid] === target) { return mid; } else if (start >= end) { break; } else if (arr[mid] > target) { end = mid - 1; } else { start = mid + 1; } mid = Math.floor((start + end) / 2); } // Return the closest between the last value checked and it's surrounding neighbors const first = Math.max(mid - 1, 0); const neighbors = arr.slice(first, mid + 2); const best = neighbors.reduce((b, el) => Math.abs(el - target) < Math.abs(b - target) ? el : b); return first + neighbors.indexOf(best); } const closestValue = myArray[binaryClosestIdx(myArray, 80)]; console.log(closestValue);
工作原理:
它将目标值与数组的中间元素进行比较。如果中间的元素更大,我们可以忽略它后面的每个元素,因为它们会更大。同样,如果中间的元素更小,我们可以忽略它之前的所有元素。 如果找到了目标值,则返回它,否则将最后测试的值与其周围的相邻值进行比较,因为最近的值只能在这3个值之间。
其他回答
如果数组像你的例子中那样排序,你可以使用二进制搜索来获得O(log n)更好的时间复杂度。
const myArray = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; const binaryClosestIdx = (arr, target) => { let start = 0; let end = arr.length - 1; let mid = Math.floor((start + end) / 2); while (1) { if (arr[mid] === target) { return mid; } else if (start >= end) { break; } else if (arr[mid] > target) { end = mid - 1; } else { start = mid + 1; } mid = Math.floor((start + end) / 2); } // Return the closest between the last value checked and it's surrounding neighbors const first = Math.max(mid - 1, 0); const neighbors = arr.slice(first, mid + 2); const best = neighbors.reduce((b, el) => Math.abs(el - target) < Math.abs(b - target) ? el : b); return first + neighbors.indexOf(best); } const closestValue = myArray[binaryClosestIdx(myArray, 80)]; console.log(closestValue);
工作原理:
它将目标值与数组的中间元素进行比较。如果中间的元素更大,我们可以忽略它后面的每个元素,因为它们会更大。同样,如果中间的元素更小,我们可以忽略它之前的所有元素。 如果找到了目标值,则返回它,否则将最后测试的值与其周围的相邻值进行比较,因为最近的值只能在这3个值之间。
对于一个较小的范围,最简单的方法是有一个map数组,例如,用你的例子来说,第80个条目的值是82。对于一个更大、更稀疏的范围,可能的方法是二分搜索。
使用查询语言,您可以查询与输入数字任意一侧有一定距离的值,然后对结果减少的列表进行排序。但是SQL并没有一个“下一个”或“上一个”的好概念,来给你一个“干净”的解决方案。
我对一个类似问题的回答是考虑关系,它是在纯Javascript中,尽管它不使用二进制搜索,所以它是O(N)而不是O(logN):
var searchArray= [0, 30, 60, 90];
var element= 33;
function findClosest(array,elem){
var minDelta = null;
var minIndex = null;
for (var i = 0 ; i<array.length; i++){
var delta = Math.abs(array[i]-elem);
if (minDelta == null || delta < minDelta){
minDelta = delta;
minIndex = i;
}
//if it is a tie return an array of both values
else if (delta == minDelta) {
return [array[minIndex],array[i]];
}//if it has already found the closest value
else {
return array[i-1];
}
}
return array[minIndex];
}
var closest = findClosest(searchArray,element);
https://stackoverflow.com/a/26429528/986160
这个解决方案使用ES5存在量词数组#some,它允许在满足条件时停止迭代。
与array# reduce相反,它不需要为一个结果迭代所有元素。
在回调中,获取搜索值与实际项之间的绝对增量,并与最后的增量进行比较。如果大于或等于,迭代将停止,因为所有其他具有delta的值都大于实际值。
如果回调中的增量较小,则实际的项被分配给结果,增量保存在lastDelta中。
最后,取具有相等增量的较小值,如下面22的示例,结果为2。
如果有更大的优先级值,delta检查必须从以下更改:
if (delta >= lastDelta) {
to:
if (delta > lastDelta) {
// ^^^ without equal sign
这将得到22,结果为42(较大值的优先级)。
这个函数需要数组中排序的值。
优先级较小的代码:
function closestValue(array, value) { var result, lastDelta; array.some(function (item) { var delta = Math.abs(value - item); if (delta >= lastDelta) { return true; } result = item; lastDelta = delta; }); return result; } var data = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; console.log(21, closestValue(data, 21)); // 2 console.log(22, closestValue(data, 22)); // 2 smaller value console.log(23, closestValue(data, 23)); // 42 console.log(80, closestValue(data, 80)); // 82
优先级较高的代码:
function closestValue(array, value) { var result, lastDelta; array.some(function (item) { var delta = Math.abs(value - item); if (delta > lastDelta) { return true; } result = item; lastDelta = delta; }); return result; } var data = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; console.log(21, closestValue(data, 21)); // 2 console.log(22, closestValue(data, 22)); // 42 greater value console.log(23, closestValue(data, 23)); // 42 console.log(80, closestValue(data, 80)); // 82
O(n)时间复杂度的一个更简单的方法是在数组的一次迭代中完成。此方法用于未排序的数组。
下面是一个javascript的例子,在这里我们从数组中找到最接近“58”的数字。
var inputArr = [150, 5, 200, 50, 30]; Var搜索= 58; var min = Math.min(); Var结果= 0; (我= 0;< inputArr.length; + +) { let absVal =数学。abs(search - inputArr[i]) if(min > absVal) { min = absVal; result = inputArr[i]; } } console.log(结果);//如果输入为58,则期望输出为50
这也适用于正数,负数,小数。
Math.min()将返回Infinity。
结果将存储离搜索元素最近的值。