163

Mam liczbę od minus 1000 do plus 1000 i mam tablicę z liczbami. Lubię to:

[2, 42, 82, 122, 162, 202, 242, 282, 322, 362]

Chcę, aby liczba, którą otrzymałem, zmieniła się na najbliższą liczbę w tablicy.

Na przykład otrzymuję 80numer, który chcę, aby otrzymał 82.

javascript arrays Nowicjusz
źródło

2

Niemożliwie proste: odłóż na bok zmienną x, przejrzyj tablicę jeden po drugim, porównaj iz bieżącą liczbą w tablicy, jeśli różnica między nią a ijest mniejsza niż aktualna wartość w x, ustaw xaktualny numer tablicy. Po zakończeniu xma numer najbliższy itablicy.

deceze

208

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);

Rozwiń fragment

Joe Grund
źródło

1

Wadą jest to, że działa tylko wtedy, gdy callback reduktora jest wywoływany z tego samego zakresu, co zadeklarowane vars. Ponieważ nie możesz przejść goaldo redukcji, musisz odwołać się do niego z zakresu globalnego.

7yl4r

5

może użyć do tego funkcji wyższego rzędu.

dmp

3

@ 7yl4r lub zawinąć go w funkcję? ;)

Dominic

1

@ 7yl4r niezupełnie ... możesz użyć bind, aby to osiągnąć ... ---------- // reduktor.js funkcja reduktor (goal, prev, curr) {return (Math.abs (curr - goal) <Math.abs (prev - goal)? curr: prev); } // main.js var counts = [4, 9, 15, 6, 2], goal = 5; counts.reduce (reduktor.bind (null, goal)); ---------- Nie wiem jak wstawić kod w komentarzach hahaha.

Mauricio Soares

Powoduje to iterację po każdym elemencie, co nie jest optymalne, jeśli lista jest uporządkowana, ale jest ok dla małych list. Nawet bez wyszukiwania binarnego pętla mogłaby się zakończyć, jeśli następna liczba jest dalej drogą.

Dominic

144

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 curr

Po 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 H

Jak 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ć.

paxdiablo
źródło

2

@micha, dodałem równoważny kod JS do odpowiedzi, zajęło mi to trochę czasu, zanim zmieniłem język z jednego, do którego byłem bardziej przyzwyczajony :-)

paxdiablo

2

Słabe środowisko wykonawcze tego algorytmu, jeśli masz duże zbiory danych.

ylun.ca

4

@ ylun.ca, ponieważ nie ma wyraźnego stwierdzenia w pytaniu, że dane są posortowane (przykład jest posortowany, ale może to być zbieg okoliczności), nie można uzyskać lepszej wydajności niż O (n). W każdym razie dla zbioru danych tej wielkości wydajność jest przeważnie nieistotna. Ale twój punkt widzenia jest ważny, więc dodam uwagi na ten temat, aby, miejmy nadzieję, uzupełnić odpowiedź.

paxdiablo

1

Dziękuję, chciałbym móc zagłosować za więcej niż raz! Więcej odpowiedzi na temat przepełnienia stosu powinno wymagać tego rodzaju wysiłku.

Richard Vanbergen,

48

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);

Rozwiń fragment

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]);

Joe Grund
źródło

24

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));

Rozwiń fragment

Umesh Patil
źródło

8

Im wiecej tym lepiej.

Hot Licks

6

Twierdziłbym, że jest to lepsze rozwiązanie, ponieważ wykorzystuje tylko JavaScript. Zaakceptowana odpowiedź wykorzystuje jQuery, o którym nie wspominano w pierwotnym pytaniu, i którego inne osoby badające to pytanie mogą nie używać.

Sean the Bean

17

Działa z niesortowanymi tablicami

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 82

W 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.

Dan Mindru
źródło

1

Nie wiem, ale wydaje mi się, że można mieć wątpliwości co do wydajności, ponieważ jest to praktycznie 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ą.

noob

1

Tak, wspaniale jest widzieć, jak się uczysz! Nawiasem mówiąc, mówiłem tylko o wątpliwościach dotyczących wydajności, nie twierdząc, że faktycznie działa gorzej, ale sprawdziłem liczby dla ciebie, a twoje 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ą.)

noob

1

Rekwizyty za proste rozwiązanie. Działa świetnie w moim przypadku użycia (nie mam luksusu posiadania wstępnie posortowanej tablicy, jak robi to

Noob

2

Można zrobić findClosest powrócić redukuj funkcji zwrotnej, aby go do wielokrotnego użytku na wszystkich tablicach: const findClosest = goal => (a,b) => Math.abs(a - goal) < Math.abs(b - goal) ? a : b;

Jakob E

1

Przykład: [2, 42, 82, 122, 162, 202, 242, 282, 322, 362].reduce(findClosest(80))

Jakob E

11

W przypadku tablic posortowanych (wyszukiwanie liniowe)

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));

Rozwiń fragment

Zauważ, że algorytm można znacznie ulepszyć, np. Używając drzewa binarnego.

Hubert Grześkowiak
źródło

Chociaż ta strategia jest dobra, ma kilka błędów. Przykład a[i]lub i[0].

Wesley Workman,

1

Dzięki, @WesleyWorkman. Właśnie je naprawiłem. Mam nadzieję, że mam wszystko. Nawiasem mówiąc, możesz także edytować odpowiedzi innych osób.

Hubert Grzeskowiak

Gdzie muszę dokonać korekty w powyższym kodzie, na który udzielono odpowiedzi, aby uzyskać najbliższą wyższą wartość? Przykład: [110, 111, 120, 140, 148, 149, 155, 177, 188, 190] Jeśli wyszukuję 150, powinienem otrzymać 155, a nie 149. Próbowałem, ale znalazłem trudności w rozwiązaniu tego. Czy mógłbyś mi pomóc. Dzięki

user1199842,

9

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);
});

// 5

Gajus
źródło

1

Rzeczywiście, dużo bardziej na temat. ale aby „uzyskać najbliższą liczbę z tablicy”, nadal musisz wybrać pierwszy element z posortowanej tablicy.

Shaya Ulman

6

W 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 sign

Dałoby 22to wynik 42(priorytet większych wartości).

Ta funkcja wymaga posortowanych wartości w tablicy.

Kod z priorytetem mniejszych wartości:

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

Rozwiń fragment

Kod z priorytetem większych wartości:

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)); // 82

Rozwiń fragment

Nina Scholz
źródło

Więc zakładasz, że podana tablica jest posortowana ... To oszczędza ci piekielnie dużo czasu.

Redu

1

tablica op wygląda na posortowaną, więc tak :)

Nina Scholz

Pierwsze rozwiązanie nie działa na danych wejściowych, które zawierają dwukrotnie tę samą liczbę. np.closestValue([ 2, 2, 42, 80 ], 50) === 2

Sébastien Vercammen

@ SébastienVercammen, dane op są unikalne i posortowane.

Nina Scholz

@NinaScholz OP określił tylko: „Mam tablicę z liczbami” i „Chcę, aby liczba, którą otrzymałem, zmieniła się na najbliższą liczbę z tablicy” . Przykładowa tablica była tylko jednym przykładem. Tablica nie gwarantuje unikalnych wpisów.

Sébastien Vercammen

4

ES6

Działa z tablicami posortowanymi i niesortowanymi

Liczby liczb całkowitych i zmiennoprzecinkowych, mile widziane ciągi znaków

/**
 * 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

Sébastien
źródło

3

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 !

FrenchieFred
źródło

1

A co z dolną granicą? Zawsze używasz następnej wyższej wartości. Ale twoje podejście przypomina mi goog.math.clamp(zamknięcie Google) tylko z tablicami i bez dbania o dolną granicę.

noob

Twoje rozwiązanie zwraca następną większą liczbę z tablicy. Nie znaleziono najbliższej ani dokładnej wartości.

Hubert Grzeskowiak

2

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);

https://stackoverflow.com/a/26429528/986160

Michail Michailidis
źródło

2

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.

Jon
źródło

Hej, czy możesz wyjaśnić, dlaczego to jest improved for loop? Odwrócone pętle nie zawsze poprawiają wydajność.

A1rPun

Oceniasz .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

Jon

Zaktualizowałem odpowiedź. Zmieniłem to na while. Teraz jest jeszcze szybszy.

Jon

0

Działałoby nieco zmodyfikowane wyszukiwanie binarne w tablicy.

Holygeek
źródło

3

Ojej, to dziwne - najwyraźniej ktoś nie lubi wyszukiwań binarnych. (Nawet pomyślałem, że to najlepsze ogólne rozwiązanie.)

Hot Licks

0

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.

Hot Licks
źródło

0

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;
  });
}

Vikas
źródło

0

#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
źródło

0

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);

Rozwiń fragment

Można to również uruchomić na nieprymitywach, np closest(data, 21, item => item.age)

Zmień findna, findIndexaby zwrócić indeks w tablicy.

Dominic
źródło

A co z nieuporządkowaną tablicą?

EdG

W przypadku nieuporządkowanych wybierz jedno z rozwiązań, które nie wychodzi, jednak jeśli wykonujesz tę pracę wiele razy, bardziej optymalne może być jednokrotne posortowanie tablicy. Jak wspomniano, jeśli tablica jest naprawdę duża, wyszukiwanie binarne będzie bardziej wydajne niż liniowe.

Dominic

0

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));

M Abdullah
źródło

-5

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;
    }
}

DeadPool
źródło

Post poprosił o javascript w tagach

Shannon Hochkins

uzyskać najbliższą liczbę z tablicy

Odpowiedzi:

Działa z niesortowanymi tablicami

W przypadku tablic posortowanych (wyszukiwanie liniowe)

Kod z priorytetem mniejszych wartości:

Kod z priorytetem większych wartości:

Działa z tablicami posortowanymi i niesortowanymi

Liczby liczb całkowitych i zmiennoprzecinkowych, mile widziane ciągi znaków