我有一个从负1000到正1000的数字，还有一个包含数字的数组。就像这样：
[2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
我希望获得的数字能够变为数组中最接近它的数字。
例如，如果我输入数字80，我希望它变成82。
从数组中获取最接近的数字
268
- noob
2
21个回答
3
一种时间复杂度为O(n)的更简单的方法是在一个数组遍历中完成。这种方法适用于未排序的数组。
以下是一个JavaScript示例，从数组中找到最接近“58”的数字。
var inputArr = [150, 5, 200, 50, 30];
var search = 58;
var min = Math.min();
var result = 0;
for(i=0;i<inputArr.length;i++) {
let absVal = Math.abs(search - inputArr[i])
if(min > absVal) {
min=absVal;
result = inputArr[i];
}
}
console.log(result); //expected output 50 if input is 58这将适用于正数、负数和小数。
Math.min()将返回Infinity。
result将存储与搜索元素最接近的值。
- varad_s
2
我对类似问题的回答也考虑了平局，而且使用纯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);
- Michail Michailidis
1
如果数组像您的示例一样排序，则可以使用二分查找来获得更好的时间复杂度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);工作原理：
它将目标值与数组的中间元素进行比较。如果中间元素更大，我们可以忽略它后面的每个元素，因为它们将更大。同样，如果中间元素更小，我们可以忽略它前面的每个元素。
如果找到目标值，则返回它；否则，我们将最后测试的值与其周围的邻居进行比较，因为最接近的值只能在这三个值之间。
- DevAb
4
为什么在第5行添加
start和end，当时start将是0？ - Sujal Singh不确定我是否理解了你的问题，但在 while 循环中，我们将
start 或 end 设置为 mid。
通过这样做，我们从数组中删除了当前检查值之前或之后的每个元素。 - DevAb在 while 循环中这样做是有意义的，但是在初始化
start 时，为什么不直接使用 Math.floor(end/2) 呢？或者我漏掉了什么？ - Sujal Singh1哦，这只是为了代码可读性，因此它看起来与 while 循环中的
mid = Math.floor((start + end) / 2); 相同，但说实话我不确定它是否真的更好。 - DevAb1
最有效的方法是二分查找。然而，即使是简单的解决方案，当下一个数字与当前数字相距较远时也可能退出。几乎所有的解决方案都没有考虑到数组是有序的，并且需要遍历整个数组 :/
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);这也适用于非基元类型，例如：closest(data, 21, item => item.age)
将find更改为findIndex以返回数组中的索引。
- Dominic
3
无序数组怎么办？ - EdG
对于无序的情况，可以选择其中一个不存在的解决方案。但是，如果您需要多次执行此操作，则一次对数组进行排序可能更加优化。正如所提到的，如果数组非常大，则二分查找比线性查找更有效率。 - Dominic
1如果你有一个包含1,000,000个对象的数组，二分查找最多只需要19次比较就能找出任何数字。然而，这里提供的解决方案平均需要500,000次比较，最多可能需要1,000,000次。是的，这是一种性能调整，但我不认为代码复杂度能够证明它的正确性。 - 话虽如此，我怀疑
Math.abs 对你的解决方案是否真正必要。如果有什么问题，我觉得它会破坏那些同时包含正负数的数组的函数。 - bvdb1
我喜欢Fusion的方法，但其中有一个小错误。像这样才是正确的：
function closest(array, number) {
var num = 0;
for (var i = array.length - 1; i >= 0; i--) {
if(Math.abs(number - array[i]) < Math.abs(number - array[num])){
num = i;
}
}
return array[num];
}
它也更快，因为它使用了改进的
for 循环。
最后我像这样编写了我的函数：
var getClosest = function(number, array) {
var current = array[0];
var difference = Math.abs(number - current);
var index = array.length;
while (index--) {
var newDifference = Math.abs(number - array[index]);
if (newDifference < difference) {
difference = newDifference;
current = array[index];
}
}
return current;
};
我使用console.time()进行了测试，结果比另一个函数稍微快一些。
- Jon
3
嘿，你能解释一下为什么这是一个“改进的for循环”吗？反向循环并不总是性能提升。 - A1rPun
在这个循环中，你只评估了一次
.length，即当你声明i时。但我认为var i = arr.length; while (i--) {}会更快。 - Jon我更新了我的答案。我把它改成了“while”。现在它更快了。 - Jon
1
我不知道是否应该回答一个旧问题，但由于这篇文章在谷歌搜索中排名第一，所以我希望你能原谅我在这里添加我的解决方案和个人见解。
因为懒惰，我不相信这个问题的解决方案会是一个循环，所以我继续搜索并找到了过滤函数：
var myArray = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
var myValue = 80;
function BiggerThan(inArray) {
return inArray > myValue;
}
var arrBiggerElements = myArray.filter(BiggerThan);
var nextElement = Math.min.apply(null, arrBiggerElements);
alert(nextElement);
这是全部内容！
- FrenchieFred
2
2那么下限呢？你总是使用下一个更高的值。但是你的方法让我想起了
goog.math.clamp（Google Closure），只不过是针对数组而不是考虑下限。 - noob1你的解决方案从数组中返回下一个更高的数字。既不找到最接近的值，也不找到精确的值。 - Hubert Grzeskowiak
0
在数组中找到两个最接近的数字
function findTwoClosest(givenList, goal) {
var first;
var second;
var finalCollection = [givenList[0], givenList[1]];
givenList.forEach((item, firtIndex) => {
first = item;
for (let i = firtIndex + 1; i < givenList.length; i++) {
second = givenList[i];
if (first + second < goal) {
if (first + second > finalCollection[0] + finalCollection[1]) {
finalCollection = [first, second];
}
}
}
});
return finalCollection;
}
var counts = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
var goal = 80;
console.log(findTwoClosest(counts, goal));
- mabdullahse
1
1请留下一些评论。例如，“2个最接近的数字”的定义是什么？它可能意味着不同的事情。您是指围绕“目标”最接近的2个数字，还是真正指最小偏差的2个数字？假设您指的是后者，我想知道为什么您会想要其中的2个数字。我的意思是，在像
[0, 1, 2, 33, 35]这样的数组中，在搜索30时，您是否希望得到[33, 35]？您计划稍后对它们进行平均，以得出34的结果吗？ - bvdb-1
这里还有另一种变体，它连接头和脚形成一个循环范围，并仅接受给定输入的最小值。这对我获取加密算法之一的字符代码值非常有帮助。
function closestNumberInCircularRange(codes, charCode) {
return codes.reduce((p_code, c_code)=>{
if(((Math.abs(p_code-charCode) > Math.abs(c_code-charCode)) || p_code > charCode) && c_code < charCode){
return c_code;
}else if(p_code < charCode){
return p_code;
}else if(p_code > charCode && c_code > charCode){
return Math.max.apply(Math, [p_code, c_code]);
}
return p_code;
});
}
- Vikas
-1
您可以使用以下逻辑来查找最接近的数字，而不使用reduce函数
let arr = [0, 80, 10, 60, 20, 50, 0, 100, 80, 70, 1];
const n = 2;
let closest = -1;
let closeDiff = -1;
for (let i = 0; i < arr.length; i++) {
if (Math.abs(arr[i] - n) < closeDiff || closest === -1) {
closeDiff = Math.abs(arr[i] - n);
closest = arr[i];
}
}
console.log(closest);
- Manpreet Singh
1
-1
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
class CompareFunctor
{
public:
CompareFunctor(int n) { _n = n; }
bool operator()(int & val1, int & val2)
{
int diff1 = abs(val1 - _n);
int diff2 = abs(val2 - _n);
return (diff1 < diff2);
}
private:
int _n;
};
int Find_Closest_Value(int nums[], int size, int n)
{
CompareFunctor cf(n);
int cn = *min_element(nums, nums + size, cf);
return cn;
}
int main()
{
int nums[] = { 2, 42, 82, 122, 162, 202, 242, 282, 322, 362 };
int size = sizeof(nums) / sizeof(int);
int n = 80;
int cn = Find_Closest_Value(nums, size, n);
cout << "\nClosest value = " << cn << endl;
cin.get();
}
- Rushikesh
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
x，逐个遍历数组中的元素，将i与当前数组元素进行比较，如果它们之间的差小于x当前的值，就将x设为当前的数组元素。当遍历完成后，x就是数组中距离i最近的数字。 - deceze