我有一个从负1000到正1000的数字，还有一个包含数字的数组。就像这样：
[2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
我希望获得的数字能够变为数组中最接近它的数字。
例如，如果我输入数字80，我希望它变成82。
从数组中获取最接近的数字
268
- noob
2
21个回答
315
ES5版本：
var counts = [4, 9, 15, 6, 2],
goal = 5;
var closest = counts.reduce(function(prev, curr) {
return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
});
console.log(closest);- Joe Grund
5
1缺点是只有在reduce的回调函数从声明变量的相同作用域中调用时才能正常工作。由于无法将“goal”传递给reduce，因此必须从全局作用域引用它。 - 7yl4r
9可以使用高阶函数来完成这个操作。 - danp
6@7yl4r 或者将其封装在一个函数中？ ;) - Dominic
2@7yl4r 不是很准确...你可以使用bind来实现这个...
// reducer.js function reducer(goal, prev, curr) { return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev); }
// reducer.js function reducer(goal, prev, curr) { return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev); }
// main.js var counts = [4, 9, 15, 6, 2], goal = 5; counts.reduce(reducer.bind(null, goal));
哈哈哈，我不知道如何在评论中放置代码。 - Mauricio Soares2这会迭代每个项目，如果列表已排序，则不是最佳选择，但对于小型列表来说还可以。即使没有二进制搜索，如果下一个数字更远，则循环也可能退出。 - Dominic
167
以下是伪代码，可以转换成任何过程式语言：
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>
它基本上使用二分法搜索（bracketing）和检查中间值来每次减半解决方案空间，这是一个经典的 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
就像之前说的一样，这对于小数据集或不需要快速运行的任务来说没有太大影响，但这是您可能想考虑的一种选择。
- paxdiablo
5
2@micha，我已经在答案中添加了等效的JS代码，只是从我更熟悉的语言转换需要一些时间 :-) - paxdiablo
2如果你有大型数据集，这个算法的运行时间会很差。 - ylun.ca
4由于问题中没有明确说明数据已排序（示例已排序但可能是巧合），因此您无法获得比O（n）更好的效率。无论如何，对于这样大小的数据集，效率大多是无关紧要的。但是您提出的观点是正确的，所以我会添加相关注释，希望能使答案更完整。 - paxdiablo
1谢谢，我希望我能够多次点赞！Stack Overflow上的更多答案应该付出这种努力。 - Richard Vanbergen
1你在这个答案中付出的努力真是太棒了，非常感谢你提供这些图表，它们让理解变得更容易。 - visylvius
111
ES6（ECMAScript 2015）版本：
const counts = [4, 9, 15, 6, 2];
const goal = 5;
const output = counts.reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
console.log(output);为了实现可重用性，您可以使用支持占位符的柯里化函数进行封装(http://ramdajs.com/0.19.1/docs/#curry或https://lodash.com/docs#curry)。这样可以根据需要提供很大的灵活性：
const getClosest = _.curry((counts, goal) => {
return counts.reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
});
const closestToFive = getClosest(_, 5);
const output = closestToFive([4, 9, 15, 6, 2]);
console.log(output);<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.20/lodash.min.js"></script>- Joe Grund
26
以下是可工作的代码：
var array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
function closest(array, num) {
var i = 0;
var minDiff = 1000;
var ans;
for (i in array) {
var m = Math.abs(num - array[i]);
if (m < minDiff) {
minDiff = m;
ans = array[i];
}
}
return ans;
}
console.log(closest(array, 88));- Umesh Patil
2
7我认为这是更好的解决方案，因为它只使用了JavaScript。被采纳的答案使用了jQuery，而原问题中没有提到，其他查看此问题的人可能也没有使用jQuery。 - Sean the Bean
1如果你在数组
[1, 2, 3] 中寻找最接近 5000 的数字，那么你会大吃一惊。 - paxdiablo22
适用于未排序数组
尽管这里发布了一些好的解决方案，但JavaScript是一种灵活的语言，它为我们提供了许多不同的解决问题的工具。
当然，这完全取决于您的编码风格。如果您的代码更加函数化，您会发现reduce方法很适合，例如：
arr.reduce(function (prev, curr) {
return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
});
然而，有些人可能会发现这很难阅读，这取决于他们的编码风格。因此，我建议采用一种新的解决问题的方法：
var findClosest = function (x, arr) {
var indexArr = arr.map(function(k) { return Math.abs(k - x) })
var min = Math.min.apply(Math, indexArr)
return arr[indexArr.indexOf(min)]
}
findClosest(80, [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]) // Outputs 82
与使用Math.min.apply查找最小值的其他方法相反，这个方法不要求输入数组arr是已排序的。我们不需要关心索引或者事先进行排序。
我会逐行解释代码以便更清晰明了：
arr.map(function(k) { return Math.abs(k - x) })创建一个新的数组，实际上存储了给定数字（在arr中的数字）减去输入数字（x）的绝对值。我们接下来将寻找最小的数字（也是最接近输入数字的数字）。Math.min.apply(Math, indexArr)这是一种合法的方法来查找我们刚创建的数组中最小的数字（没有更多含义）。arr[indexArr.indexOf(min)]这可能是最有趣的部分。我们已经找到了最小的数字，但我们不确定是否应该添加或减去初始数字（x）。那是因为我们使用Math.abs()来查找差异。然而，array.map创建了一个输入数组的映射，保持索引在同一位置。因此，为了找到最接近的数字，我们只需返回找到的最小值在给定数组中的索引indexArr.indexOf(min)。
- Dan Mindru
7
1请给出下投票者，请解释为什么这不是一个好答案或者为什么你不认为它合适。谢谢。 - Dan Mindru
1是的，很高兴看到你在学习！顺便说一下，我只是谈到了性能上的疑虑，并没有争论它实际上表现得更差，但我已经为你跑了一些数字，发现与@paxdiablo的O(log n)比较，您的O(n)解决方案在随机数上执行的操作次数少了约10万次/秒。设计算法时，总是先排序为好（除非您知道自己在做什么，并且有基准数据支持您）。 - noob
1简单的解决方案很棒。对于我的用例非常有效（我没有像新手那样拥有预排序的数组的奢侈条件）。 - jaggedsoft
2你可以将findClosest返回一个reduce回调函数，使其可在所有数组上重复使用：
const findClosest = goal => (a,b) => Math.abs(a - goal) < Math.abs(b - goal) ? a : b; - Jakob E1
[2, 42, 82, 122, 162, 202, 242, 282, 322, 362].reduce(findClosest(80)) - Jakob E显示剩余2条评论
15
所有的解决方案都被过度设计了。
实际上很简单：
const needle = 5;
const haystack = [1, 2, 3, 4, 5, 6, 7, 8, 9];
haystack.sort((a, b) => {
return Math.abs(a - needle) - Math.abs(b - needle);
})[0];
// 5
- Gajus
3
2这样做效率非常低。 - bumbeishvili
5我需要在一个包含20,000多个数字的列表中找到最接近的数字，并且可能需要经常执行此操作（可能每次用户得分时都需要）。我还需要在两个维度上进行操作，也就是说，在两个非常长的列表中找到两个最接近的数字。 "过度设计" 是相对于需求而言的。我发现这里的一切都没有满足我的要求。 - Kyle Baker
@KyleBaker 没问题，如果你知道你的列表可能很大，那么应该寻找一个高效的实现。如果列表不是很大，就没有必要过度设计或过早优化。这个答案肯定能够满足大部分需求。而且有一个问题是不要对原始数组进行排序，只需要复制它：
[...haystack].sort(... - Andre Figueiredo13
对于已排序的数组(线性搜索)
到目前为止，所有的答案都集中在整个数组的搜索上。 考虑到您的数组已经排序并且您只想要最接近的数字，这可能是最简单的（但不是最快的）解决方案:
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));请注意，算法可以通过使用二叉树等方式大大改进。
- Hubert Grzeskowiak
4
虽然这个策略不错，但是有几个拼写错误。例如，
a[i]或者i[0]。 - Wesley Workman1谢谢，@WesleyWorkman。我刚刚修复了它们。希望我都搞定了。顺便说一句，你也可以编辑别人的答案。 - Hubert Grzeskowiak
在上面的代码中，我需要进行哪些更正才能获得更接近的高值？例如：[110, 111, 120, 140, 148, 149, 155, 177, 188, 190] 如果我搜索150，我应该得到155而不是149。我尝试过了，但是在解决这个问题时遇到了困难。你能帮忙吗？谢谢。 - user1199842
你说这可能是最快的，然后又说它可以大大改进。 - Kyle Baker
10
ES6
适用于排序和未排序的数组
支持数字整数和浮点数、字符串
/**
* Finds the nearest value in an array of numbers.
* Example: nearestValue(array, 42)
*
* @param {Array<number>} arr
* @param {number} val the ideal value for which the nearest or equal should be found
*/
const nearestValue = (arr, val) => arr.reduce((p, n) => (Math.abs(p) > Math.abs(n - val) ? n - val : p), Infinity) + val
例子：
let values = [1,2,3,4,5]
console.log(nearestValue(values, 10)) // --> 5
console.log(nearestValue(values, 0)) // --> 1
console.log(nearestValue(values, 2.5)) // --> 2
values = [100,5,90,56]
console.log(nearestValue(values, 42)) // --> 56
values = ['100','5','90','56']
console.log(nearestValue(values, 42)) // --> 56
- Sébastien
7
这个解决方案使用ES5 存在量词 Array#some，它允许在满足条件时停止迭代。
与Array#reduce相反，它不需要为一个结果迭代所有元素。
在回调函数中，将搜索值和实际项之间的绝对delta进行比较，并与上一个delta进行比较。如果大于或等于，则停止迭代，因为所有其他值及其delta都大于实际值。
如果回调中的delta更小，则将实际项分配给结果，并将delta保存在lastDelta中。
最后，取相等delta的较小值，就像下面的22示例中一样，结果为2。
if (delta >= lastDelta) {
至：
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- Nina Scholz
5
所以你假设给定的数组是已排序的...这可以节省你大量的时间。 - Redu
1这个OP的数组看起来已经排好序了，所以是的 :) - Nina Scholz
第一种解决方案在包含相同数字的输入上会出现错误。例如：
closestValue([ 2, 2, 42, 80 ], 50) === 2。 - Sébastien Vercammen@SébastienVercammen，OP的数据是唯一且已排序的。 - Nina Scholz
@NinaScholz OP 只确定了“我有一个包含数字的数组”和“我希望我得到的数字改变为数组中最接近的数字”。示例数组只是一个示例。数组不能保证唯一条目。 - Sébastien Vercammen
7
其他答案建议您需要遍历整个数组：
- 计算每个元素的偏差
- 跟踪最小偏差及其元素
- 最后，在遍历整个数组后，返回该具有最小偏差的元素。
如果数组已经排序，这就没有意义了。没有必要计算所有偏差。例如，在一个包含1百万个元素的有序集合中，您只需要计算约19个偏差（最多）即可找到您的匹配项。您可以使用二分搜索方法来完成此操作：
function findClosestIndex(arr, element) {
let from = 0, until = arr.length - 1
while (true) {
const cursor = Math.floor((from + until) / 2);
if (cursor === from) {
const diff1 = element - arr[from];
const diff2 = arr[until] - element;
return diff1 <= diff2 ? from : until;
}
const found = arr[cursor];
if (found === element) return cursor;
if (found > element) {
until = cursor;
} else if (found < element) {
from = cursor;
}
}
}
结果：
console.log(findClosestIndex([0, 1, 2, 3.5, 4.5, 5], 4));
// output: 3
console.log(findClosestIndex([0, 1, 2, 3.49, 4.5, 5], 4));
// output: 4
console.log(findClosestIndex([0, 1, 2, 3.49, 4.5, 5], 90));
// output: 5
console.log(findClosestIndex([0, 1, 2, 3.49, 4.5, 5], -1));
// output: 0
- bvdb
2
2很想知道为什么这个回答被踩了；- 我试图改进回答，解释为什么这是一个更好的答案。 - bvdb
1谢谢！对于一个不熟悉数据结构和算法，但需要在排序数组中进行大量搜索的人来说... 这非常有帮助。它比其他朴素算法快得多。我无法自己实现这个，但是你给的样例运行得非常完美。谢谢！！ - i-know-nothing
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
x，逐个遍历数组中的元素，将i与当前数组元素进行比较，如果它们之间的差小于x当前的值，就将x设为当前的数组元素。当遍历完成后，x就是数组中距离i最近的数字。 - deceze