我有一个从- 1000到+ 1000的数我有一个数组，里面都是数字。是这样的:
[2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
我想让我得到的数字变成数组中最接近的数字。
例如，我的数字是80，我希望它是82。
当前回答
下面是伪代码，可以转换成任何过程语言:
array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
number = 112
print closest (number, array)
def closest (num, arr):
curr = arr[0]
foreach val in arr:
if abs (num - val) < abs (num - curr):
curr = val
return curr
它只是计算出给定数字和每个数组元素之间的绝对差值，然后返回差值最小的一个。
对于示例值:
number = 112 112 112 112 112 112 112 112 112 112
array = 2 42 82 122 162 202 242 282 322 362
diff = 110 70 30 10 50 90 130 170 210 250
|
+-- one with minimal absolute difference.
作为概念的证明，下面是我用来演示这一点的Python代码:
def closest (num, arr):
curr = arr[0]
for index in range (len (arr)):
if abs (num - arr[index]) < abs (num - curr):
curr = arr[index]
return curr
array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
number = 112
print closest (number, array)
而且，如果你真的需要它在Javascript中，请参阅下面的完整HTML文件，其中演示了该函数的操作:
<html>
<head></head>
<body>
<script language="javascript">
function closest (num, arr) {
var curr = arr[0];
var diff = Math.abs (num - curr);
for (var val = 0; val < arr.length; val++) {
var newdiff = Math.abs (num - arr[val]);
if (newdiff < diff) {
diff = newdiff;
curr = arr[val];
}
}
return curr;
}
array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
number = 112;
alert (closest (number, array));
</script>
</body>
</html>
现在请记住，如果数据项已经排序(这可以从示例数据中推断出来，但您没有显式地说明)，则可能存在提高效率的空间。例如，您可以使用二分搜索来查找最接近的项。
您还应该记住，除非您需要每秒执行多次，否则效率的提高基本上是不明显的，除非您的数据集变得更大。
如果你确实想尝试这种方式(并且可以保证数组按升序排序)，这是一个很好的起点:
<html>
<head></head>
<body>
<script language="javascript">
function closest (num, arr) {
var mid;
var lo = 0;
var hi = arr.length - 1;
while (hi - lo > 1) {
mid = Math.floor ((lo + hi) / 2);
if (arr[mid] < num) {
lo = mid;
} else {
hi = mid;
}
}
if (num - arr[lo] <= arr[hi] - num) {
return arr[lo];
}
return arr[hi];
}
array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
number = 112;
alert (closest (number, array));
</script>
</body>
</html>
它基本上使用括号和中间值的检查来将每次迭代的解空间减少一半，这是一个经典的O(log N)算法，而上面的顺序搜索是O(N):
0 1 2 3 4 5 6 7 8 9 <- indexes
2 42 82 122 162 202 242 282 322 362 <- values
L M H L=0, H=9, M=4, 162 higher, H<-M
L M H L=0, H=4, M=2, 82 lower/equal, L<-M
L M H L=2, H=4, M=3, 122 higher, H<-M
L H L=2, H=3, difference of 1 so exit
^
|
H (122-112=10) is closer than L (112-82=30) so choose H
如前所述，对于小型数据集或不需要盲目快速的东西，这应该没有太大区别，但这是您可能想要考虑的一个选项。
其他回答
对于排序数组(线性搜索)
到目前为止，所有答案都集中在搜索整个数组上。 考虑到你的数组已经排序，你真的只想要最近的数字，这可能是最简单的(但不是最快的)解决方案:
var a = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; var target = 90000; /** * Returns the closest number from a sorted array. **/ function closest(arr, target) { if (!(arr) || arr.length == 0) return null; if (arr.length == 1) return arr[0]; for (var i = 1; i < arr.length; i++) { // As soon as a number bigger than target is found, return the previous or current // number depending on which has smaller difference to the target. if (arr[i] > target) { var p = arr[i - 1]; var c = arr[i] return Math.abs(p - target) < Math.abs(c - target) ? p : c; } } // No number in array is bigger so return the last. return arr[arr.length - 1]; } // Trying it out console.log(closest(a, target));
请注意，该算法可以大大改进，例如使用二叉树。
如果数组像你的例子中那样排序，你可以使用二进制搜索来获得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个值之间。
我对一个类似问题的回答是考虑关系，它是在纯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
下面是伪代码，可以转换成任何过程语言:
array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
number = 112
print closest (number, array)
def closest (num, arr):
curr = arr[0]
foreach val in arr:
if abs (num - val) < abs (num - curr):
curr = val
return curr
它只是计算出给定数字和每个数组元素之间的绝对差值，然后返回差值最小的一个。
对于示例值:
number = 112 112 112 112 112 112 112 112 112 112
array = 2 42 82 122 162 202 242 282 322 362
diff = 110 70 30 10 50 90 130 170 210 250
|
+-- one with minimal absolute difference.
作为概念的证明，下面是我用来演示这一点的Python代码:
def closest (num, arr):
curr = arr[0]
for index in range (len (arr)):
if abs (num - arr[index]) < abs (num - curr):
curr = arr[index]
return curr
array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
number = 112
print closest (number, array)
而且，如果你真的需要它在Javascript中，请参阅下面的完整HTML文件，其中演示了该函数的操作:
<html>
<head></head>
<body>
<script language="javascript">
function closest (num, arr) {
var curr = arr[0];
var diff = Math.abs (num - curr);
for (var val = 0; val < arr.length; val++) {
var newdiff = Math.abs (num - arr[val]);
if (newdiff < diff) {
diff = newdiff;
curr = arr[val];
}
}
return curr;
}
array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
number = 112;
alert (closest (number, array));
</script>
</body>
</html>
现在请记住，如果数据项已经排序(这可以从示例数据中推断出来，但您没有显式地说明)，则可能存在提高效率的空间。例如，您可以使用二分搜索来查找最接近的项。
您还应该记住，除非您需要每秒执行多次，否则效率的提高基本上是不明显的，除非您的数据集变得更大。
如果你确实想尝试这种方式(并且可以保证数组按升序排序)，这是一个很好的起点:
<html>
<head></head>
<body>
<script language="javascript">
function closest (num, arr) {
var mid;
var lo = 0;
var hi = arr.length - 1;
while (hi - lo > 1) {
mid = Math.floor ((lo + hi) / 2);
if (arr[mid] < num) {
lo = mid;
} else {
hi = mid;
}
}
if (num - arr[lo] <= arr[hi] - num) {
return arr[lo];
}
return arr[hi];
}
array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
number = 112;
alert (closest (number, array));
</script>
</body>
</html>
它基本上使用括号和中间值的检查来将每次迭代的解空间减少一半，这是一个经典的O(log N)算法，而上面的顺序搜索是O(N):
0 1 2 3 4 5 6 7 8 9 <- indexes
2 42 82 122 162 202 242 282 322 362 <- values
L M H L=0, H=9, M=4, 162 higher, H<-M
L M H L=0, H=4, M=2, 82 lower/equal, L<-M
L M H L=2, H=4, M=3, 122 higher, H<-M
L H L=2, H=3, difference of 1 so exit
^
|
H (122-112=10) is closer than L (112-82=30) so choose H
如前所述，对于小型数据集或不需要盲目快速的东西，这应该没有太大区别，但这是您可能想要考虑的一个选项。
最有效的方法是二分查找。然而，即使是简单的解决方案，当下一个数字与当前数字进一步匹配时，也可以退出。这里几乎所有的解决方案都没有考虑到数组是有序的，并且迭代整个:/
const closest = (orderedArray, value, valueGetter = item => item) => orderedArray.find((item, i) => i === orderedArray.length - 1 || Math.abs(value - valueGetter(item)) < Math.abs(value - valueGetter(orderedArray[i + 1]))); var data = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; console.log('21 -> 2', closest(data, 21) === 2); console.log('22 -> 42', closest(data, 22) === 42); // equidistant between 2 and 42, select highest console.log('23 -> 42', closest(data, 23) === 42); console.log('80 -> 82', closest(data, 80) === 82);
这也可以在非原语上运行，例如，nearest (data, 21, item => item.age)
将find更改为findIndex以返回数组中的索引。
