У меня есть число от минус 1000 до плюс 1000, и у меня есть массив с числами в нем. Нравится:
[2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
Я хочу, чтобы число, которое у меня было, изменилось до ближайшего числа в массиве.
Например, я получаю 80 как число, я хочу получить 82.
Версия 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);goal для уменьшения, вы должны ссылаться на него из глобальной области.
- person 7yl4r; 06.02.2015
Вот псевдокод, который должен быть преобразован в любой процедурный язык:
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
Как уже говорилось, это не должно иметь большого значения для небольших наборов данных или для вещей, которым не требуется быть ослепительно быстрыми, но это вариант, который вы, возможно, захотите рассмотреть.
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/[email protected]/lodash.min.js"></script>Рабочий код, как показано ниже:
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));5000 в массиве [1, 2, 3], вас ждет грубый шок.
- person paxdiablo; 17.11.2020
Хотя здесь были опубликованы несколько хороших решений, JavaScript - это гибкий язык, который дает нам инструменты для решения проблемы множеством различных способов. Конечно, все зависит от вашего стиля. Если ваш код более функциональный, вы найдете подходящим вариантом уменьшения вариаций, т. Е .:
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).Я создал bin, демонстрирующий это.
3n, и это ES5, хотя вы отвечаете в 2016 году, и другие решения просто прекрасны, хотя этот нуб, который задал этот вопрос, явно не был программистом в то время .
- person noob; 10.10.2016
const (в чем смысл функции стрелки?). Кто-то может возразить, что это даже не читается. Вдобавок ко всему, я сомневаюсь, что ES6 является производительным в целом, имейте в виду, что мы все еще работаем в основном с ES5 и используем Babel для транспиляции кода ES6. Наконец, я считаю нелепым довод в пользу производительности. Я призываю вас протестировать все методы и посмотреть, какой из них самый медленный в браузере. Я не знаю, сколько тестов вы провели в своей жизни, но, судя по всему, вас ждет сюрприз.
- person Dan Mindru; 10.10.2016
reduce супер мощный, но это не первое, что вы изучаете на JavaScript, и некоторым кажется, что это немного сложно понять (и не только новичкам, это сложно для большинства разработчиков без функционального фона)
- person Dan Mindru; 10.10.2016
O(n) выполняет примерно на 100 тыс. Операций в секунду меньше, чем @paxdiablo O(log n) на случайных числах. Они говорят, что при разработке алгоритма всегда сначала сортируют. (За исключением случаев, когда вы знаете, что делаете, и у вас есть контрольные точки, которые могут вас поддержать.)
- person noob; 11.10.2016
0(log n) быстрее, чем 0(n); особенно для больших наборов данных, которые я мог бы добавить (хотя сначала 0(log n) будет медленнее). Однако большинство ответов здесь не 0(log n) ????
- person Dan Mindru; 11.10.2016
const findClosest = goal => (a,b) => Math.abs(a - goal) < Math.abs(b - goal) ? a : b;
- person Jakob E; 08.02.2019
[2, 42, 82, 122, 162, 202, 242, 282, 322, 362].reduce(findClosest(80))
- person Jakob E; 08.02.2019
Все ответы на данный момент сосредоточены на поиске по всему массиву. Учитывая, что ваш массив уже отсортирован, и вам действительно нужен только ближайший номер, это, вероятно, самое быстрое решение:
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));Обратите внимание, что алгоритм можно значительно улучшить, например используя двоичное дерево.
a[i] или i[0].
- person Wesley Workman; 09.03.2017
Все решения чрезмерно продуманы.
Это очень просто:
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
Это решение использует ES5 экзистенциальный квантификатор _ 1_, что позволяет остановить итерацию, если условие встретились.
Противоположность Array#reduce, да не нужно перебирать все элементы для получения одного результата.
Внутри обратного вызова берется абсолютный delta между искомым значением и фактическим item и сравнивается с последней дельтой. Если больше или равно, итерация останавливается, потому что все другие значения с их дельтами больше фактического значения.
Если delta в обратном вызове меньше, то фактический элемент назначается результату, а delta сохраняется в lastDelta.
Наконец, берутся меньшие значения с равными дельтами, как в приведенном ниже примере 22, что приводит к 2.
Если есть приоритет больших значений, необходимо изменить дельта-проверку с:
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)); // 82function 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)); // 82closestValue([ 2, 2, 42, 80 ], 50) === 2
- person Sébastien Vercammen; 03.02.2020
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
Более простой способ с временной сложностью 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 будет хранить значение, ближайшее к элементу поиска.
Я не знаю, должен ли я отвечать на старый вопрос, но поскольку этот пост появляется первым в поиске Google, я надеялся, что вы простите мне добавление здесь моего решения и моего 2c.
Будучи ленивым, я не мог поверить, что решением этого вопроса будет LOOP, поэтому я поискал еще немного и вернулся с filter function:
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);
Это все !
goog.math.clamp (закрытие Google) только с массивами и без заботы о нижней границе.
- person noob; 06.04.2014
Мой ответ на аналогичный вопрос также учитывает связи, и он написан на простом 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
Мне нравится подход от 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(), и он немного быстрее, чем другая функция.
improved for loop? Обратные циклы не всегда улучшают производительность.
- person A1rPun; 01.03.2016
.length только один раз, когда объявляете i, тогда как для этого цикла. Но я думаю var i = arr.length;while (i--) {} было бы еще быстрее
- person Jon; 03.03.2016
while. Теперь это еще быстрее.
- person Jon; 03.03.2016
Немного измененный двоичный поиск в массиве подойдет.
Для небольшого диапазона проще всего иметь массив карты, где, например, 80-я запись будет иметь значение 82, чтобы использовать ваш пример. Для гораздо большего и разреженного диапазона, вероятно, лучше использовать двоичный поиск.
С помощью языка запросов вы можете запросить значения на некотором расстоянии по обе стороны от вашего входного числа, а затем отсортировать полученный сокращенный список. Но в SQL нет хорошего понятия «следующий» или «предыдущий», чтобы дать вам «чистое» решение.
Другой вариант, здесь у нас есть круговой диапазон, соединяющий голову до пят и принимающий только минимальное значение для данного ввода. Это помогло мне получить значения кода символа для одного из алгоритмов шифрования.
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;
});
}
Наиболее эффективным будет бинарный поиск. Однако даже простые решения могут завершиться, когда следующий номер будет дальше совпадать с текущим. Почти все решения здесь не учитывают, что массив упорядочен и повторяется, хотя все это: /
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, чтобы вернуть индекс в массиве.
Math.abs действительно необходим в вашем решении. Во всяком случае, я думаю, что это нарушает вашу функцию для массивов, которые имеют как положительные, так и отрицательные числа.
- person bvdb; 14.07.2021
Найти два ближайших числа в массиве
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));
goal? Или вы действительно имеете в виду 2 числа с наименьшим отклонением? Предполагая, что вы имеете в виду последнее, я задаюсь вопросом, зачем вам когда-либо понадобились 2 из них. Я имею в виду, что в массиве типа [0, 1, 2, 33, 35] при поиске 30 вы хотите [33, 35]? Планировали ли вы позже усреднить их, чтобы получить 34?
- person bvdb; 14.07.2021
В других ответах предполагалось, что вам нужно будет перебрать весь массив:
Если массив уже отсортирован, это не имеет смысла. Рассчитывать все отклонения нет необходимости. например в упорядоченном наборе из 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
Вот фрагмент кода для поиска ближайшего к числу элемента из массива в сложности O (nlog (n)): -
Ввод: - Элемент {1,60,0, -10,100,87,56}: - 56 Ближайшее число в массиве: - 60
Исходный код (Java):
package com.algo.closestnumberinarray;
import java.util.TreeMap;
public class Find_Closest_Number_In_Array {
public static void main(String arsg[]) {
int array[] = { 1, 60, 0, -10, 100, 87, 69 };
int number = 56;
int num = getClosestNumber(array, number);
System.out.println("Number is=" + num);
}
public static int getClosestNumber(int[] array, int number) {
int diff[] = new int[array.length];
TreeMap<Integer, Integer> keyVal = new TreeMap<Integer, Integer>();
for (int i = 0; i < array.length; i++) {
if (array[i] > number) {
diff[i] = array[i] - number;
keyVal.put(diff[i], array[i]);
} else {
diff[i] = number - array[i];
keyVal.put(diff[i], array[i]);
}
}
int closestKey = keyVal.firstKey();
int closestVal = keyVal.get(closestKey);
return closestVal;
}
}
x, пройти по массиву один за другим, сравнитьiс текущим числом в массиве, если разница между ним иiменьше текущего значения вx, установитьxна текущий номер массива . По окончанииxимеет номер, ближайший кiиз массива. - person deceze♦ schedule 21.12.2011