У меня есть число от минус 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);Здесь псевдокод, который должен быть конвертирован в любой процедурный язык:
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 (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);Рабочий код, как показано ниже:
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));Хотя здесь было несколько хороших решений, 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, этот Math.min.apply не требует сортировки входного массива arr. Нам не нужно заботиться об индексах или сортировать их заранее.
Я объясню код построчно для ясности:
arr.map(function(k) { return Math.abs(k - x) }) Создает новый массив, по существу, сохраняя абсолютные значения заданных чисел (число в arr) минус входное число (x). Далее мы будем искать наименьшее число (которое также ближе всего к вводимому номеру)Math.min.apply(Math, indexArr) Это Math.min.apply(Math, indexArr) способ найти наименьшее число в массиве, который мы только что создали (ничего более)arr[indexArr.indexOf(min)] Это, пожалуй, самая интересная часть. Мы нашли наше наименьшее число, но мы не уверены, должны ли мы добавить или вычесть начальное число (x). Это потому, что мы использовали Math.abs() чтобы найти разницу. Однако array.map создает (логически) карту входного массива, сохраняя индексы в одном месте. Поэтому, чтобы найти ближайшее число, мы просто возвращаем индекс найденного минимума в данном массиве indexArr.indexOf(min).Я создал мусорное ведро, демонстрирующее это.
Все ответы пока сосредоточены на поиске по всему массиву. Учитывая, что ваш массив уже отсортирован, и вы действительно хотите только ближайший номер, это, вероятно, самое быстрое решение:
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)); В этом решении используется экзистенциальный квантификатор ES5 Array#some, который позволяет остановить итерацию, если выполняется условие.
Оппозиция Array#reduce redund, не нужно итерировать все элементы для одного результата.
Внутри обратного вызова берется абсолютная delta между искомым значением и фактическим item и сравнивается с последней дельтой. Если больше или равно, итерация останавливается, потому что все другие значения с их дельтами больше, чем фактическое значение.
Если delta в lastDelta меньше, то фактический элемент присваивается результату, и delta сохраняется в lastDelta.
Наконец, берутся меньшие значения с равными дельтами, как в приведенном ниже примере 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Все решения перегружены.
Это так просто, как:
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);
});
// 5
Я не знаю, должен ли я отвечать на старый вопрос, но поскольку это сообщение появляется в первую очередь в поиске Google, я надеялся, что вы простите мне добавление моего решения и моего 2c здесь.
Будучи ленивым, я не мог поверить, что решение для этого вопроса было бы LOOP, поэтому я искал немного больше и вернулся с функцией фильтрации:
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);
Что все!
Мой ответ на аналогичный вопрос также учитывает связи, и он находится в простом 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);
Мне нравится подход от 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() и немного быстрее, чем другая функция.
Немного измененный бинарный поиск в массиве будет работать.
Для небольшого диапазона самое простое - иметь массив карт, где, например, 80-я запись будет иметь значение 82 в нем, чтобы использовать ваш пример. Для гораздо большего, редкого диапазона, вероятно, путь - это двоичный поиск.
С языком запроса вы можете запросить значения на некотором расстоянии от каждой стороны от вашего номера ввода, а затем отсортировать полученный результирующий список. Но SQL не имеет хорошей концепции "следующего" или "предыдущего", чтобы дать вам "чистое" решение.
Другой вариант здесь имеет круглый диапазон, соединяющий головку с носом и принимающий только минимальное значение для данного входа. Это помогло мне получить значения кода char для одного из алгоритмов шифрования.
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;
});
}
#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();
}
Вот фрагмент кода, чтобы найти ближайший элемент к числу из массива в Complexity 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;
}
}