Odpowiedzi:
Wersja 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);goaldo redukcji, musisz odwołać się do niego z zakresu globalnego.
Oto pseudokod, który można zamienić na dowolny język proceduralny:
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 currPo prostu oblicza bezwzględne różnice między podaną liczbą i każdym elementem tablicy i zwraca jedną z tych z minimalną różnicą.
Przykładowe wartości:
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.Jako dowód koncepcji, oto kod Pythona, którego użyłem do pokazania tego w akcji:
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)A jeśli naprawdę potrzebujesz tego w JavaScript, zobacz poniżej pełny plik HTML, który demonstruje tę funkcję w akcji:
<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>Teraz należy pamiętać, że może istnieć pole do poprawy wydajności, jeśli na przykład elementy danych są posortowane (co można wywnioskować z przykładowych danych, ale nie podasz tego jawnie). Możesz na przykład użyć wyszukiwania binarnego, aby znaleźć najbliższy element.
Należy również pamiętać, że jeśli nie musisz robić tego wiele razy na sekundę, poprawa wydajności będzie w większości niezauważalna, chyba że zbiory danych staną się znacznie większe.
Jeśli nie chcesz, aby spróbować go w ten sposób (i może zagwarantować, tablica jest posortowana w kolejności rosnącej), jest to dobry punkt wyjścia:
<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>Zasadniczo używa nawiasów i sprawdzania wartości środkowej, aby zmniejszyć przestrzeń rozwiązania o połowę dla każdej iteracji, klasyczny O(log N)algorytm, podczas gdy powyższe wyszukiwanie sekwencyjne wyglądało następująco 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 HJak wspomniano, nie powinno to mieć większego znaczenia w przypadku małych zestawów danych lub rzeczy, które nie muszą być oślepiająco szybkie, ale jest to opcja, którą warto rozważyć.
Wersja 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);W celu ponownego wykorzystania możesz zawinąć funkcję curry, która obsługuje symbole zastępcze ( http://ramdajs.com/0.19.1/docs/#curry lub https://lodash.com/docs#curry ). Daje to dużą elastyczność w zależności od potrzeb:
const getClosest = curry((counts, goal) => {
return counts
.reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
});
const closestTo5 = getClosest(_, 5);
const closestTo = getClosest([4, 9, 15, 6, 2]);Kod roboczy, jak poniżej:
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));Chociaż zamieszczono tutaj kilka dobrych rozwiązań, JavaScript jest elastycznym językiem, który daje nam narzędzia do rozwiązywania problemów na wiele różnych sposobów. Oczywiście wszystko zależy od Twojego stylu. Jeśli Twój kod jest bardziej funkcjonalny, wariant redukcji będzie odpowiedni, np .:
arr.reduce(function (prev, curr) {
return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
});Jednak niektórym może się to wydawać trudne do odczytania, w zależności od stylu kodowania. Dlatego proponuję nowy sposób rozwiązania problemu:
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 82W przeciwieństwie do innych podejść do znajdowania wartości minimalnej przy użyciu Math.min.apply, ta metoda nie wymaga arrsortowania tablicy wejściowej . Nie musimy przejmować się indeksami ani ich wcześniej sortować.
Dla jasności wyjaśnię kod wiersz po wierszu:
arr.map(function(k) { return Math.abs(k - x) })Tworzy nową tablicę, zasadniczo przechowującą wartości bezwzględne podanych liczb (liczba w arr) minus liczba wejściowa ( x). Następnie poszukamy najmniejszej liczby (która jest również najbliższa liczbie wejściowej)Math.min.apply(Math, indexArr) To jest legalny sposób na znalezienie najmniejszej liczby w tablicy, którą właśnie utworzyliśmy (nic więcej)arr[indexArr.indexOf(min)]To chyba najbardziej interesująca część. Znaleźliśmy naszą najmniejszą liczbę, ale nie jesteśmy pewni, czy powinniśmy dodać, czy odjąć liczbę początkową ( x). To dlatego, że kiedyś Math.abs()znajdowaliśmy różnicę. Jednak array.maptworzy (logicznie) mapę tablicy wejściowej, zachowując indeksy w tym samym miejscu. Dlatego, aby znaleźć najbliższą liczbę, po prostu zwracamy indeks znalezionego minimum w podanej tablicy indexArr.indexOf(min).Stworzyłem kosz demonstrujący to.
3nES5, mimo że odpowiadasz w 2016 roku, a inne rozwiązania są w porządku, mimo że ten noob, który zadał to pytanie, najwyraźniej nie był wówczas programistą.
O(n)rozwiązanie działa o około 100 000 operacji O(log n)na sekundę mniej niż @paxdiablo na liczbach losowych. Podczas projektowania algorytmu zawsze najpierw sortuj. (Z wyjątkiem sytuacji, gdy wiesz, co robisz i masz testy porównawcze, które Cię wspierają.)
const findClosest = goal => (a,b) => Math.abs(a - goal) < Math.abs(b - goal) ? a : b;
[2, 42, 82, 122, 162, 202, 242, 282, 322, 362].reduce(findClosest(80))
Wszystkie dotychczasowe odpowiedzi koncentrują się na przeszukiwaniu całej tablicy. Biorąc pod uwagę, że twoja tablica jest już posortowana i tak naprawdę chcesz tylko najbliższej liczby, jest to prawdopodobnie najszybsze rozwiązanie:
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));Zauważ, że algorytm można znacznie ulepszyć, np. Używając drzewa binarnego.
a[i]lub i[0].
Wszystkie rozwiązania są zbyt zaawansowane.
To jest tak proste, jak:
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);
});
// 5W rozwiązaniu tym zastosowano kwantyfikator egzystencjalny ES5 Array#some, który umożliwia zatrzymanie iteracji w przypadku spełnienia warunku.
W przeciwieństwie do tego Array#reduce, nie ma potrzeby iteracji wszystkich elementów dla jednego wyniku.
Wewnątrz wywołania zwrotnego pobierana jest deltawartość bezwzględna między wartością wyszukaną a rzeczywistą itemi porównywana z ostatnią deltą. Jeśli jest większy lub równy, iteracja zatrzymuje się, ponieważ wszystkie inne wartości z ich deltami są większe niż wartość rzeczywista.
Jeśli deltaw wywołaniu zwrotnym jest mniejszy, to do wyniku przypisywana jest aktualna pozycja i deltazapisywana w lastDelta.
Na koniec brane są mniejsze wartości z równymi deltami, jak w poniższym przykładzie 22, co skutkuje 2.
Jeśli istnieje priorytet większych wartości, kontrola delta musi zostać zmieniona z:
if (delta >= lastDelta) {do:
if (delta > lastDelta) {
// ^^^ without equal signDałoby 22to wynik 42(priorytet większych wartości).
Ta funkcja wymaga posortowanych wartości w tablicy.
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
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
Przykłady:
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
Nie wiem, czy mam odpowiedzieć na stare pytanie, ale ponieważ ten post pojawia się jako pierwszy w wyszukiwarce Google, miałem nadzieję, że wybaczysz mi dodanie tutaj mojego rozwiązania i mojego 2c.
Będąc leniwy, nie mogłem uwierzyć, że rozwiązaniem na to pytanie będzie PĘTLA, więc poszukałem trochę więcej i wróciłem z funkcją filtru :
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);To wszystko !
goog.math.clamp(zamknięcie Google) tylko z tablicami i bez dbania o dolną granicę.
Moja odpowiedź na podobne pytanie dotyczy również uwzględnienia powiązań i jest to w zwykłym JavaScript, chociaż nie używa wyszukiwania binarnego, więc jest to O (N), a nie 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);Podoba mi się podejście z Fusion, ale jest w nim mały błąd. Tak to jest poprawne:
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];
}Jest też trochę szybszy, ponieważ wykorzystuje ulepszoną forpętlę.
Na koniec napisałem swoją funkcję w ten sposób:
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;
};Przetestowałem to z console.time()i jest nieco szybszy niż druga funkcja.
improved for loop? Odwrócone pętle nie zawsze poprawiają wydajność.
.lengthtylko raz, kiedy deklarujesz i, podczas gdy dla tej pętli. Ale myślę, że var i = arr.length;while (i--) {}byłoby jeszcze szybciej
while. Teraz jest jeszcze szybszy.
Dla małego zakresu najprościej jest mieć tablicę map, w której np. 80-ty wpis miałby wartość 82, aby użyć twojego przykładu. W przypadku znacznie większego, rzadkiego zakresu prawdopodobnie najlepszym rozwiązaniem jest wyszukiwanie binarne.
Za pomocą języka zapytań można wyszukiwać wartości w pewnej odległości po obu stronach wprowadzonej liczby, a następnie sortować wynikową skróconą listę. Jednak SQL nie ma dobrego pojęcia „następny” lub „poprzedni”, aby zapewnić „czyste” rozwiązanie.
Innym wariantem jest tutaj okrągły zakres łączący głowicę z palcami i akceptujemy tylko wartość minimalną na dane wejście. Pomogło mi to uzyskać wartości kodu znaków dla jednego z algorytmów szyfrowania.
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();
}Najbardziej wydajne byłoby wyszukiwanie binarne. Jednak nawet proste rozwiązania mogą zostać rozwiązane, gdy następna liczba jest dalszą zgodnością z bieżącej . Prawie wszystkie rozwiązania tutaj nie uwzględniają tego, że tablica jest uporządkowana i iteruje przez całość: /
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);Można to również uruchomić na nieprymitywach, np closest(data, 21, item => item.age)
Zmień findna, findIndexaby zwrócić indeks w tablicy.
Aby znaleźć dwie najbliższe liczby w tablicy
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));Oto fragment kodu, aby znaleźć element najbliższy liczbie z tablicy o złożoności O (nlog (n)): -
Dane wejściowe: - {1,60,0, -10,100,87,56} Element: - 56 Najbliższa liczba w tablicy: - 60
Kod źródłowy (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, przejrzyj tablicę jeden po drugim, porównajiz bieżącą liczbą w tablicy, jeśli różnica między nią aijest mniejsza niż aktualna wartość wx, ustawxaktualny numer tablicy. Po zakończeniuxma numer najbliższyitablicy.