dapatkan nomor terdekat dari array

163

Saya memiliki angka dari minus 1000 hingga plus 1000 dan saya memiliki array dengan angka di dalamnya. Seperti ini:

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

Saya ingin nomor yang saya punya berubah menjadi nomor array terdekat.

Misalnya saya mendapatkan 80nomor yang saya inginkan 82.

javascript arrays cupu
sumber
2
Sangat sederhana: menyisihkan variabel x, melalui array satu per satu, dibandingkan idengan angka saat ini dalam array, jika perbedaan antara itu dan ilebih kecil dari nilai saat ini di x, setel xke nomor array saat ini. Setelah selesai, xmiliki nomor terdekat idari array.
tipuan

Jawaban:

208

Versi 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);
Luaskan cuplikan

Joe Grund
sumber
1
downside adalah bahwa itu hanya berfungsi jika pengurangan callback dipanggil dari lingkup yang sama dengan vars yang dideklarasikan. Karena Anda tidak dapat lulus goaluntuk mengurangi, Anda harus merujuknya dari lingkup global.
7yl4r
5
bisa menggunakan fungsi urutan yang lebih tinggi untuk melakukannya juga.
dmp
3
@ 7yl4r atau membungkusnya dalam suatu fungsi? ;)
Dominic
1
@ 7yl4r tidak benar-benar ... Anda dapat menggunakan bind untuk mencapai ini ... ---------- // reducer.js berfungsi reducer (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 (reducer.bind (null, goal)); ---------- Saya tidak tahu bagaimana memasukkan kode di komentar hahaha.
Mauricio Soares
Ini berulang setiap item yang tidak optimal jika daftar dipesan tetapi ok untuk daftar kecil. Bahkan tanpa pencarian biner, sebuah loop dapat keluar jika angka selanjutnya adalah jalan yang lebih jauh.
Dominic
144

Inilah pseudo-code yang harus dapat dikonversi menjadi bahasa prosedural apa pun:

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

Itu hanya berhasil membedakan mutlak antara jumlah yang diberikan dan setiap elemen array dan memberi Anda kembali salah satu yang dengan perbedaan minimal.

Untuk nilai contoh:

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.

Sebagai bukti konsep, inilah kode Python yang saya gunakan untuk menunjukkan ini dalam tindakan:

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)

Dan jika kau benar - benar membutuhkannya dalam Javascript, lihat di bawah untuk file HTML lengkap yang menunjukkan fungsi dalam aksi:

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

Sekarang ingatlah bahwa mungkin ada ruang untuk peningkatan efisiensi jika, misalnya, item data Anda diurutkan (yang dapat disimpulkan dari data sampel tetapi Anda tidak secara eksplisit menyatakannya). Anda bisa, misalnya, menggunakan pencarian biner untuk menemukan item terdekat.

Anda juga harus mengingatnya, kecuali Anda harus melakukannya berkali- kali per detik, peningkatan efisiensi sebagian besar tidak akan terlihat kecuali set data Anda menjadi jauh lebih besar.

Jika kamu tidak ingin mencoba cara itu (dan dapat menjamin array diurutkan dalam urutan menaik), ini adalah baik titik awal:

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

Ini pada dasarnya menggunakan tanda kurung dan memeriksa nilai tengah untuk mengurangi ruang solusi hingga setengahnya untuk setiap iterasi, sebuah O(log N)algoritma klasik sedangkan pencarian berurutan di atas adalah 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

Seperti yang dinyatakan, itu seharusnya tidak membuat banyak perbedaan untuk dataset kecil atau untuk hal-hal yang tidak perlu terlalu cepat, tetapi ini adalah opsi yang mungkin ingin Anda pertimbangkan.

paxdiablo
sumber
2
@micha, saya telah menambahkan kode JS eqivalent ke jawabannya, hanya perlu beberapa saat untuk mengubah bahasa dari yang sebelumnya saya gunakan :-)
paxdiablo
2
Runtime yang buruk untuk algoritme ini jika Anda memiliki kumpulan data besar.
ylun.ca
4
@ ylun.ca, karena tidak ada pernyataan eksplisit dalam pertanyaan bahwa data diurutkan (contoh diurutkan tetapi itu mungkin kebetulan), Anda tidak bisa mendapatkan efisiensi yang lebih baik daripada O (n). Dalam kasus apa pun, untuk kumpulan data yang sebesar itu, efisiensi sebagian besar tidak relevan. Tapi poin Anda valid, jadi saya akan menambahkan catatan untuk efek tersebut agar mudah-mudahan jawabannya lebih lengkap.
paxdiablo
1
Terima kasih, saya berharap saya bisa lebih baik sekali! Lebih banyak jawaban tentang stack overflow harus dimasukkan ke dalam upaya semacam ini.
Richard Vanbergen
48

Versi 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);
Luaskan cuplikan

Untuk dapat digunakan kembali, Anda dapat membungkus fungsi kari yang mendukung tempat penampung ( http://ramdajs.com/0.19.1/docs/#curry atau https://lodash.com/docs#curry ). Ini memberikan banyak fleksibilitas tergantung pada apa yang Anda butuhkan:

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
sumber
24

Kode kerja seperti di bawah ini:

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

Umesh Patil
sumber
8
Semakin meriah.
Hot Licks
6
Saya berpendapat ini adalah solusi yang lebih baik karena hanya menggunakan JavaScript. Jawaban yang diterima menggunakan jQuery, yang tidak disebutkan dalam pertanyaan asli, dan orang lain yang melihat pertanyaan ini mungkin tidak menggunakan.
Sean the Bean
17

Bekerja dengan array yang tidak disortir

Meskipun ada beberapa solusi bagus yang diposting di sini, JavaScript adalah bahasa yang fleksibel yang memberi kami alat untuk menyelesaikan masalah dengan berbagai cara. Itu semua bermuara pada gaya Anda, tentu saja. Jika kode Anda lebih fungsional, Anda akan menemukan pengurangan variasi yang cocok, yaitu:

  arr.reduce(function (prev, curr) {
    return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
  });

Namun, beberapa orang mungkin kesulitan membaca, tergantung pada gaya pengkodeannya. Karena itu saya mengusulkan cara baru untuk menyelesaikan masalah:

  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

Bertentangan dengan pendekatan lain yang menemukan nilai minimum menggunakan Math.min.apply, ini tidak memerlukan array input arruntuk diurutkan . Kami tidak perlu peduli dengan indeks atau mengurutkannya sebelumnya.

Saya akan menjelaskan kode baris demi baris untuk kejelasan:

  1. arr.map(function(k) { return Math.abs(k - x) })Menciptakan array baru, pada dasarnya menyimpan nilai absolut dari angka yang diberikan (angka masuk arr) dikurangi angka input ( x). Kami akan mencari nomor terkecil berikutnya (yang juga paling dekat dengan nomor input)
  2. Math.min.apply(Math, indexArr) Ini adalah cara yang sah untuk menemukan angka terkecil dalam array yang baru saja kita buat sebelumnya (tidak lebih dari itu)
  3. arr[indexArr.indexOf(min)]Ini mungkin bagian yang paling menarik. Kami telah menemukan angka terkecil kami, tetapi kami tidak yakin apakah kami harus menambah atau mengurangi angka awal ( x). Itu karena kami dulu Math.abs()menemukan perbedaannya. Namun, array.mapmembuat (secara logis) peta larik input, menjaga indeks di tempat yang sama. Oleh karena itu, untuk mengetahui nomor terdekat kami hanya mengembalikan indeks minimum yang ditemukan dalam array yang diberikan indexArr.indexOf(min).

Saya telah membuat nampan yang menunjukkannya.

Dan Mindru
sumber
1
Saya tidak tahu, tetapi saya kira orang mungkin memiliki keraguan kinerja karena ini praktis 3ndan ES5 meskipun Anda menjawab pada tahun 2016 dan solusi lain baik-baik saja meskipun noob ini yang mengajukan pertanyaan ini jelas bukan programmer pada saat itu.
noob
1
Ya, senang melihat Anda belajar! Ngomong-ngomong, saya hanya berbicara tentang keraguan kinerja, tidak berargumen bahwa itu benar-benar berkinerja lebih buruk, tetapi saya menjalankan angka untuk Anda dan O(n)solusi Anda berkinerja sekitar 100k ops / dtk kurang dari @paxdiablo O(log n)pada angka acak. Saat mendesain suatu algoritma selalu mengurutkan terlebih dahulu yang mereka katakan. (Kecuali jika Anda tahu apa yang Anda lakukan dan Anda memiliki tolok ukur untuk mendukung Anda.)
noob
1
Alat peraga untuk solusi sederhana. Bekerja sangat baik untuk kasus penggunaan saya (saya tidak memiliki kemewahan memiliki array pra-diurutkan seperti noob.)
jaggedsoft
2
Anda dapat membuat findClosest mengembalikan fungsi pengurangan panggilan balik agar dapat digunakan kembali di semua array: const findClosest = goal => (a,b) => Math.abs(a - goal) < Math.abs(b - goal) ? a : b;
Jakob E
1
Contoh: [2, 42, 82, 122, 162, 202, 242, 282, 322, 362].reduce(findClosest(80))
Jakob E
11

Untuk array yang diurutkan (pencarian linear)

Semua jawaban sejauh ini berkonsentrasi pada pencarian melalui seluruh array. Mengingat array Anda sudah diurutkan dan Anda benar-benar hanya ingin nomor terdekat ini mungkin solusi tercepat:

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

Perhatikan bahwa algoritme dapat sangat ditingkatkan misalnya menggunakan pohon biner.

Hubert Grzeskowiak
sumber
Meskipun strategi di sini baik, ini memiliki beberapa kesalahan ketik. Contoh, a[i]atau i[0].
Wesley Workman
1
Terima kasih, @WesleyWorkman. Perbaiki saja. Saya harap saya mendapatkan semuanya. Omong-omong, Anda juga dapat mengedit jawaban orang lain.
Hubert Grzeskowiak
Di mana saya perlu melakukan koreksi pada kode jawab di atas untuk mendapatkan nilai terdekat yang lebih tinggi? Contoh: [110, 111, 120, 140, 148, 149, 155, 177, 188, 190] Jika saya mencari 150, saya akan mendapatkan 155 bukan 149. Saya mencoba tetapi menemukan kesulitan dalam menyelesaikannya. Bisakah Anda membantu? Terima kasih
user1199842
9

Semua solusi over-engineered.

Sesederhana:

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
sumber
1
Memang, lebih tepatnya. tetapi untuk "mendapatkan nomor terdekat dari array" Anda masih harus memilih elemen pertama dari array yang diurutkan.
Shaya Ulman
6

Solusi ini menggunakan ES5 quantential quantifier Array#some , yang memungkinkan untuk menghentikan iterasi, jika suatu kondisi terpenuhi.

Sebaliknya Array#reduce, itu tidak perlu mengulangi semua elemen untuk satu hasil.

Di dalam callback, absolut deltaantara nilai yang dicari dan aktualitem diambil dan dibandingkan dengan delta terakhir. Jika lebih besar atau sama, iterasi berhenti, karena semua nilai lain dengan delta mereka lebih besar dari nilai sebenarnya.

Jika deltadalam panggilan balik lebih kecil, maka item yang sebenarnya ditetapkan untuk hasilnya dan deltadisimpan dalam lastDelta.

Akhirnya, nilai yang lebih kecil dengan delta yang sama diambil, seperti dalam contoh di bawah ini 22, yang menghasilkan 2.

Jika ada prioritas nilai yang lebih besar, cek delta harus diubah dari:

if (delta >= lastDelta) {

untuk:

if (delta > lastDelta) {
//       ^^^ without equal sign

Ini akan sesuai dengan 22, hasilnya42 (Prioritas nilai yang lebih besar).

Fungsi ini membutuhkan nilai yang diurutkan dalam array.

Kode dengan prioritas nilai yang lebih kecil:

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
Luaskan cuplikan

Kode dengan prioritas nilai yang lebih besar:

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
Luaskan cuplikan

Nina Scholz
sumber
Jadi Anda menganggap bahwa array yang diberikan diurutkan ... Itu menyelamatkan Anda dari banyak waktu.
Redu
1
array op terlihat diurutkan, jadi ya :)
Nina Scholz
Solusi pertama istirahat pada input yang berisi angka yang sama dua kali. egclosestValue([ 2, 2, 42, 80 ], 50) === 2
Sébastien Vercammen
@ SébastienVercammen, data op unik dan diurutkan.
Nina Scholz
@NinaScholz OP hanya menentukan "Saya memiliki array dengan angka di dalamnya" dan "Saya ingin nomor yang saya punya berubah ke nomor array terdekat" . Contoh array hanyalah salah satu contoh. Array tidak menjamin entri unik.
Sébastien Vercammen
4

ES6

Bekerja dengan array yang diurutkan dan tidak disortir

Bilangan Integer dan Mengapung, String disambut

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

Contoh:

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
sumber
3

Saya tidak tahu apakah saya seharusnya menjawab pertanyaan lama, tetapi karena posting ini muncul pertama kali di pencarian Google, saya berharap Anda akan memaafkan saya menambahkan solusi saya & 2c saya di sini.

Menjadi malas, saya tidak percaya bahwa solusi untuk pertanyaan ini adalah LOOP, jadi saya mencari lebih banyak dan kembali dengan fungsi filter :

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

Itu saja !

FrenchieFred
sumber
1
Jadi bagaimana dengan batas bawah? Anda selalu menggunakan nilai selanjutnya yang lebih tinggi. Tetapi pendekatan Anda mengingatkan saya pada goog.math.clamp(penutupan google) hanya dengan array dan tanpa peduli dengan batas bawah.
noob
Solusi Anda mengembalikan angka lebih tinggi berikutnya dari array. Baik nilai terdekat maupun nilai tepatnya tidak ditemukan.
Hubert Grzeskowiak
2

Jawaban saya untuk pertanyaan serupa adalah akuntansi untuk ikatan juga dan itu dalam Javascript biasa, meskipun tidak menggunakan pencarian biner sehingga itu adalah O (N) dan bukan 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
sumber
2

Saya suka pendekatan dari Fusion, tetapi ada kesalahan kecil di dalamnya. Seperti itu benar:

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

Itu juga sedikit lebih cepat karena menggunakan forloop yang ditingkatkan .

Pada akhirnya saya menulis fungsi saya seperti ini:

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

Saya mengujinya console.time()dan sedikit lebih cepat daripada fungsi lainnya.

Jon
sumber
Hei, bisakah Anda menjelaskan mengapa itu improved for loop? Loop terbalik tidak selalu merupakan peningkatan kinerja.
A1rPun
Anda mengevaluasi .lengthhanya sekali, ketika Anda menyatakan i, sedangkan untuk loop ini. Tapi saya pikir var i = arr.length;while (i--) {}akan lebih cepat
Jon
Saya memperbarui jawaban saya. Saya mengubahnya menjadi while. Sekarang bahkan lebih cepat.
Jon
0

Pencarian biner yang sedikit dimodifikasi pada array akan bekerja.

holygeek
sumber
3
Wah, itu aneh - rupanya seseorang tidak suka pencarian biner. (Bahkan berpikir itu solusi umum terbaik.)
Hot Licks
0

Untuk rentang kecil, hal yang paling sederhana adalah memiliki larik peta, di mana, misalnya entri ke-80 akan memiliki nilai 82 di dalamnya, untuk menggunakan contoh Anda. Untuk rentang yang jauh lebih besar, jarang, mungkin cara untuk pergi adalah pencarian biner.

Dengan bahasa kueri, Anda dapat meminta nilai agak jauh di kedua sisi nomor input Anda dan kemudian menyortir daftar yang berkurang. Tetapi SQL tidak memiliki konsep "berikutnya" atau "sebelumnya" yang baik, untuk memberi Anda solusi "bersih".

Hot Licks
sumber
0

Varian lain di sini kami memiliki jangkauan melingkar yang menghubungkan kepala dan kaki dan hanya menerima nilai minimum untuk input yang diberikan. Ini membantu saya mendapatkan nilai kode char untuk salah satu algoritma enkripsi.

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;
  });
}
Vara
sumber
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
sumber
0

Yang paling efisien adalah pencarian biner. Namun bahkan solusi sederhana dapat keluar ketika nomor berikutnya adalah pertandingan lebih lanjut dari saat ini . Hampir semua solusi di sini tidak memperhitungkan array yang dipesan dan mengulangi semuanya: /

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

Ini dapat dijalankan pada non-primitif juga misalnya closest(data, 21, item => item.age)

Ubah findke findIndexuntuk mengembalikan indeks dalam array.

Dominic
sumber
Bagaimana dengan array yang tidak terurut?
EdG
Untuk unordered ambil salah satu solusi yang tidak keluar, namun jika Anda melakukan pekerjaan berulang kali maka mungkin lebih optimal untuk mengurutkan array sekali. Seperti disebutkan jika array benar-benar besar maka pencarian biner akan lebih efisien daripada yang linear.
Dominic
0

Untuk Menemukan Dua Nomor Terdekat dalam array

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
sumber
-5

Berikut ini cuplikan kode untuk menemukan elemen terdekat ke nomor dari array di Complexity O (nlog (n)): -

Input: - {1,60,0, -10,100,87,56} Elemen: - 56 Nomor Terdekat dalam Array: - 60

Kode Sumber (Jawa):

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;
    }
}
Kolam kematian
sumber
Posting meminta javascript dalam tag
Shannon Hochkins