Ho un numero da meno 1000 a più 1000 e ho un array con i numeri. In questo modo:ottiene il numero più prossimo dall'array
[2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
Voglio che il numero che ho ottenuto cambi al numero più vicino della matrice.
Per esempio ottengo 80 come numero voglio esso per ottenere 82.
Una ricerca binaria leggermente modificata sull'array funzionerebbe.
Gee, è bizzarro - a quanto pare a qualcuno non piacciono le ricerche binarie. (Anche se pensavo che fosse la migliore soluzione generale.) –
Per un intervallo di piccole dimensioni, la cosa più semplice è disporre di un array di mappe, in cui, ad esempio, l'80esimo ingresso avrà il valore 82 in esso, per utilizzare l'esempio. Per una gamma molto più ampia e sparsa, probabilmente la strada da percorrere è una ricerca binaria.
Con un linguaggio di query è possibile eseguire query per valori a una certa distanza da entrambi i lati del numero di input e quindi ordinare l'elenco ridotto risultante. Ma SQL non ha un buon concetto di "prossimo" o "precedente", per darti una soluzione "pulita".
Ecco il pseudo-codice che dovrebbe essere convertibile in qualsiasi linguaggio procedurale:
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
Funziona semplicemente le differenze assolute tra il numero dato e ogni elemento dell'array e restituisce uno di quelli con il differenza minima.
Per i valori di esempio:
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.
Come una prova di concetto, ecco il codice Python che ho usato per mostrare in azione:
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)
E, se si davvero bisogno in Javascript, vedi sotto per un file HTML completo che dimostra la funzione in azione:
<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>
Ora tenere a mente ci può essere spazio per una maggiore efficienza se, ad esempio, i vostri elementi di dati sono ordinati (che potrebbe essere dedotto dai dati di esempio, ma voi non esplicitamente dichiararlo). Ad esempio, è possibile utilizzare una ricerca binaria per trovare l'elemento più vicino.
Si deve anche tenere a mente che, a meno che non avete bisogno di farlo molte volte al secondo, i miglioramenti di efficienza saranno prevalentemente unnoticable a meno che i set di dati ottengono molto più grande.
Se fai vogliono provare in questo modo (e in grado di garantire l'array è ordinato in ordine crescente), questo è un buon punto di partenza:
<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>
Esso utilizza fondamentalmente bracketing e il controllo della valore medio di ridurre lo spazio delle soluzioni della metà per ogni iterazione, un classico algoritmo O(log N) considerando che la ricerca sequenziale sopra è stato 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
Come detto, che non dovrebbe fare molta differenza per dataset di piccole dimensioni o per cose che non hanno bisogno di per essere accecantemente veloce, ma è un'opzione che potresti voler prendere in considerazione.
@micha, ho aggiunto il codice JS eqivalent alla risposta, ci è voluto un po 'di tempo per cambiare le lingue da una che ero più abituato a :-) – paxdiablo
Scadente runtime per questo algoritmo se disponi di set di dati di grandi dimensioni. –
@ ylun.ca, poiché nella domanda non esiste un'istruzione _explicit_ che i dati siano ordinati (l'esempio è ordinato ma può essere una coincidenza), non è possibile ottenere un rendimento migliore di O (n). In ogni caso, per un set di dati di queste dimensioni, l'efficienza è per lo più irrilevante. Ma il tuo punto è valido, quindi aggiungerò delle note a tale effetto per sperare di rendere la risposta più completa. – paxdiablo
codice di lavoro, come di seguito:
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;
}
alert(closest(array,88));
Più siamo meglio è. –
Direi che questa è una soluzione migliore perché usa solo JavaScript. La risposta accettata utilizza jQuery, che non è stata menzionata nella domanda originale e che altri utenti potrebbero non utilizzare. –
ES5 Versione:
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);Questo è abbastanza NEAT. –
lato negativo è che funziona solo se callback di reduce è chiamato dallo stesso scope dei vars dichiarati. Dal momento che non puoi passare a 'goal' per ridurlo, devi fare riferimento ad esso da un ambito globale. – 7yl4r
potrebbe utilizzare una funzione di ordine superiore per fare anche questo. – dmp
non so se dovrei rispondere a una vecchia questione, ma come questo post appare per primo nelle ricerche di Google, spero che mi perdoneresti l'aggiunta della mia soluzione & my 2c qui.
essere pigro, non riuscivo a credere che la soluzione per questa domanda sarebbe un LOOP, così ho cercato un po 'di più ed è tornato con 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);
Questo è tutto!
Allora, che cos'è il limite inferiore? Usi sempre il prossimo valore più alto. Ma il tuo approccio mi ricorda 'goog.math.clamp' (google closure) solo con gli array e senza preoccuparsi del limite inferiore. – noob
La soluzione restituisce il successivo numero più alto dall'array. Né il più vicino né il valore esatto vengono trovati. –
Tutte le risposte finora concentrarsi sulla ricerca attraverso l'intero array. Considerando l'array è ordinato già e si vuole veramente solo il numero più vicino questa è probabilmente la soluzione più veloce:
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(arr, target));
Si noti che l'algoritmo può essere notevolmente migliorato per esempio usando un albero binario.
Mentre questa strategia è buona, questo ha diversi refusi. Esempio, 'a [i]' o 'i [0]'. –
Grazie, @WesleyWorkman. Li ho appena sistemati Spero di aver ottenuto tutto. A proposito, puoi anche modificare le risposte degli altri. –
Dove devo fare la correzione nel codice sopra risposto per ottenere il valore più alto più vicino? Esempio: [110, 111, 120, 140, 148, 149, 155, 177, 188, 190] Se cerco 150, dovrei ottenere 155 non 149. Ho provato, ma trovando difficoltà nel risolvere questo. Potresti per favore aiutare. Grazie – user1199842
La mia risposta a una domanda simile è contabilità per i legami troppo ed è in pianura JavaScript, anche se non fa uso di ricerca binaria quindi è O (N) e non O (log N):
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);
ES6 (2015) Versione:
const counts = [4, 9, 15, 6, 2];
const goal = 5;
counts
.reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
Per riutilizzabilità si può avvolgere in una funzione di curry che supporta segnaposto (o http://ramdajs.com/0.19.1/docs/#curryhttps://lodash.com/docs#curry). Questo dà un sacco di flessibilità a seconda di quello che vi serve:
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]);
Mi piace l'approccio da Fusion, ma c'è un piccolo errore in esso.Come che sia corretto:
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];
}
E 'anche un po' più veloce perché usa il miglioramento for loop.
Alla fine ho scritto la mia funzione come questa:
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;
};
ho provato con console.time() ed è leggermente più veloce rispetto agli altri funzioni.
Ehi, puoi spiegare perché è un 'improved for loop'? I loop invertiti non sono sempre un miglioramento delle prestazioni. – A1rPun
Valutate '.length' solo una volta, quando dichiarate' i', mentre per questo ciclo. Ma penso 'var i = arr.length; while (i--) {}' sarebbe ancora più veloce – Jon
Ho aggiornato la mia risposta. L'ho cambiato in 'while'. Ora è ancora più veloce. – Jon
Mentre ci sono stati alcuni buone soluzioni postato qui, JavaScript è un linguaggio flessibile che ci dà gli strumenti per risolvere un problema in molti modi diversi. Tutto dipende dal tuo stile, ovviamente. Se il codice è più funzionale, troverete il reduce variation adatto, cioè .:
arr.reduce(function (prev, curr) {
return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
});
Tuttavia, alcuni potrebbero trovare difficile da leggere, a seconda del loro stile di codifica. Perciò io propongo un nuovo modo di risolvere il problema:
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([2, 42, 82, 122, 162, 202, 242, 282, 322, 362], 80) // Outputs 82
Contrariamente a other approaches trovare il valore minimo utilizzando Math.min.apply, questo non richiede l'array di input arr da ordinare. Non abbiamo bisogno di preoccuparci degli indici o di ordinarli in anticipo.
Spiegherò il codice riga per riga per chiarezza:
arr.map(function(k) { return Math.abs(k - x) }) crea un nuovo array, memorizzare essenzialmente i valori assoluti dei numeri dati (numero in arr) meno il numero di input (x) . Cercheremo il numero più piccolo successivo (che è anche il più vicino al numero di input)Math.min.apply(Math, indexArr) Questo è un modo valido per trovare il numero più piccolo nell'array appena creato (niente di più)arr[indexArr.indexOf(min)] Questa è forse la parte più interessante. Abbiamo trovato il nostro numero più basso, ma non siamo sicuri di dover aggiungere o sottrarre il numero iniziale (x). Questo perché abbiamo usato Math.abs() per trovare la differenza. Tuttavia, array.map crea (logicamente) una mappa dell'array di input, mantenendo gli indici nella stessa posizione. Pertanto, per scoprire il numero più vicino, restituiamo l'indice del minimo trovato nell'array dato indexArr.indexOf(min).Ho creato un bin dimostrandolo.
Downvoters, per favore spiega perché questa non è una buona risposta o perché non la trovi adatta. Grazie. –
Non lo so, ma immagino che uno possa avere dubbi sulle prestazioni poiché questo è praticamente "3n" ed è ES5 anche se rispondi nel 2016 e altre soluzioni vanno bene anche se questo noob che ha fatto questa domanda chiaramente non era un programmatore al tempo. – noob
IMHO, non vedo come la versione ES6 della risposta lo renda migliore, tranne per l'uso di 'const' (qual è il punto della funzione freccia?). Qualcuno potrebbe obiettare che non è ancora più leggibile. Inoltre, dubito che ES6 sia performante in termini di ATM, tenete presente che stiamo ancora eseguendo principalmente ES5 e utilizzando Babel per trascrivere il codice ES6. Infine, penso che l'argomento della performance sia ridicolo. Vi sfido a confrontare tutti i metodi e vedere quale è il più lento in un browser. Non so quanti benchmark hai fatto nella tua vita, ma a quanto pare - sei sorpreso. –
Questa è una proposta con un ES5 existential quantifierArray#some, che consente di interrompere l'iterazione se viene soddisfatta una condizione.
Contrasto di Array#reduce, non è necessario iterare tutti gli elementi per un risultato.
All'interno del callback, uno delta assoluto tra il valore cercato e lo item effettivo viene preso e confrontato con l'ultimo delta. Se maggiore o uguale, l'iterazione si interrompe, poiché tutti gli altri valori con i loro delta sono maggiori del valore effettivo.
Se lo delta nella richiamata è più piccolo, l'elemento effettivo viene assegnato al risultato e lo delta viene salvato da lastDelta.
Nel risultato, vengono presi valori più piccoli con uguali delta, come nell'esempio seguente di 22, che risulta in 2.
Se v'è una priorità di valori superiori, il controllo del delta deve essere cambiato da
if (delta >= lastDelta) {
a
if (delta > lastDelta) {
// ^^^ without equal sign
Questo otterrebbe con 22, il risultato 42 (Priorità dei valori maggiori).
Questa funzione richiede i valori ordinati nell'array.
codice con priorità dei valori minori:
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)); // 82codice con priorità dei valori maggiori
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)); // 82Quindi presumi che l'array specificato sia ordinato ... Questo ti salva da un sacco di tempo. – Redu
l'array dell'op appare ordinato, quindi sì :) –
Un'altra variante qui abbiamo un intervallo circolare che collega testa a piede e accetta solo un valore minimo per un dato input. Questo mi ha aiutato a ottenere i valori del codice char per uno degli algoritmi di crittografia.
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;
});
}
È impossibile solo se non si prova nulla. Che cosa hai provato? –
Semplicemente impossibile: mettere da parte una variabile 'x', passare attraverso l'array uno per uno, confrontare' i' con il numero corrente dell'array, se la differenza tra esso e 'i' è minore del valore corrente in' x ', imposta' x' sul numero di array corrente. Al termine, 'x' ha il numero più vicino a' i' dall'array. – deceze