Bagaimana mencari indeks di mana nombor berada dalam array dalam JavaScript

Menyusun adalah konsep yang sangat penting semasa menulis algoritma. Terdapat pelbagai jenis: jenis gelembung, jenis shell, jenis blok, jenis sisir, jenis koktel, jenis gnome - Saya tidak membuat ini!

Cabaran ini memberi kita gambaran mengenai dunia yang indah. Kita harus menyusun susunan nombor dari yang paling kecil hingga yang paling besar dan mengetahui di mana nombor tertentu akan berada dalam larik itu.

Arahan algoritma

Kembalikan indeks terendah di mana nilai (argumen kedua) harus dimasukkan ke dalam array (argumen pertama) setelah disusun. Nilai yang dikembalikan harus berupa nombor. Sebagai contoh, getIndexToIns([1,2,3,4], 1.5)harus kembali 1kerana lebih besar daripada 1(indeks 0), tetapi kurang dari 2(indeks 1). Begitu juga, getIndexToIns([20,3,5], 19)harus kembali 2kerana setelah array disusun, ia akan kelihatan seperti [3,5,20]dan 19kurang dari 20(indeks 2) dan lebih besar daripada 5(indeks 1).
function getIndexToIns(arr, num) { return num; } getIndexToIns([40, 60], 50);

Kes Ujian yang Disediakan

  • getIndexToIns([10, 20, 30, 40, 50], 35)harus kembali 3.
  • getIndexToIns([10, 20, 30, 40, 50], 35) harus mengembalikan nombor.
  • getIndexToIns([10, 20, 30, 40, 50], 30)harus kembali 2.
  • getIndexToIns([10, 20, 30, 40, 50], 30) harus mengembalikan nombor.
  • getIndexToIns([40, 60], 50)harus kembali 1.
  • getIndexToIns([40, 60], 50) harus mengembalikan nombor.
  • getIndexToIns([3, 10, 5], 3)harus kembali 0.
  • getIndexToIns([3, 10, 5], 3) harus mengembalikan nombor.
  • getIndexToIns([5, 3, 20, 3], 5)harus kembali 2.
  • getIndexToIns([5, 3, 20, 3], 5) harus mengembalikan nombor.
  • getIndexToIns([2, 20, 10], 19)harus kembali 2.
  • getIndexToIns([2, 20, 10], 19) harus mengembalikan nombor.
  • getIndexToIns([2, 5, 10], 15)harus kembali 3.
  • getIndexToIns([2, 5, 10], 15) harus mengembalikan nombor.
  • getIndexToIns([], 1)harus kembali 0.
  • getIndexToIns([], 1) harus mengembalikan nombor.

Penyelesaian # 1: .sort (), .indexOf ()

PEDAC

Memahami Masalah : Kami mempunyai dua input, susunan, dan nombor. Tujuan kami adalah untuk mengembalikan indeks nombor input kami setelah disusun ke dalam array input.

Contoh / Kes Ujian : Orang baik di freeCodeCamp tidak memberitahu kami dengan cara mana array input harus disusun, tetapi kes ujian yang disediakan menjelaskan bahawa array input harus disusun dari yang paling kecil hingga yang paling besar.

Perhatikan bahawa terdapat casing tepi pada dua kes ujian terakhir yang disediakan di mana array input adalah array kosong.

Struktur Data : Oleh kerana kita akhirnya mengembalikan indeks, berpegang pada tatasusunan akan berfungsi untuk kita.

Kami akan menggunakan kaedah bagus bernama .indexOf():

.indexOf()mengembalikan indeks pertama di mana elemen hadir dalam array, atau -1jika elemen tersebut tidak ada sama sekali. Sebagai contoh:

let food = ['pizza', 'ice cream', 'chips', 'hot dog', 'cake']
food.indexOf('chips')// returns 2food.indexOf('spaghetti')// returns -1

Kami juga akan menggunakan .concat()di sini dan bukannya .push(). Kenapa? Kerana apabila anda menambahkan elemen ke array menggunakan .push(), ia mengembalikan panjang array baru. Apabila anda menambahkan elemen ke array menggunakan .concat(), ia mengembalikan array baru itu sendiri. Sebagai contoh:

let array = [4, 10, 20, 37, 45]
array.push(98)// returns 6array.concat(98)// returns [4, 10, 20, 37, 45, 98]

Algoritma :

  1. Masukkan numke arr.
  2. Isih arrdari yang paling kecil hingga yang paling besar.
  3. Kembalikan indeks dari num.

Kod : Lihat di bawah!

function getIndexToIns(arr, num) { // Insert num into arr, creating a new array. let newArray = arr.concat(num) // [40, 60].concat(50) // [40, 60, 50] // Sort the new array from least to greatest. newArray.sort((a, b) => a - b) // [40, 60, 50].sort((a, b) => a - b) // [40, 50, 60] // Return the index of num which is now // in the correct place in the new array. return newArray.indexOf(num); // return [40, 50, 60].indexOf(50) // 1 } getIndexToIns([40, 60], 50);

Tanpa pemboleh ubah dan komen tempatan:

function getIndexToIns(arr, num) { return arr.concat(num).sort((a, b) => a - b).indexOf(num); } getIndexToIns([40, 60], 50);

Penyelesaian # 2: .sort (), .findIndex ()

PEDAC

Memahami Masalah : Kami mempunyai dua input, susunan, dan nombor. Tujuan kami adalah untuk mengembalikan indeks nombor input kami setelah disusun ke dalam array input.

Contoh / Kes Ujian : Orang baik di freeCodeCamp tidak memberitahu kami dengan cara mana array input harus disusun, tetapi kes ujian yang disediakan menjelaskan bahawa array input harus disusun dari yang paling kecil hingga yang paling besar.

Terdapat dua kes yang perlu diambil kira dengan penyelesaian ini:

  1. Sekiranya array input kosong maka kita perlu kembali 0kerana numakan menjadi satu- satunya elemen dalam array itu, oleh itu pada indeks 0.
  2. Sekiranya numberada di hujung yang arrdiurutkan dari yang paling kecil hingga yang paling besar, maka kita perlu mengembalikan panjangnya arr.

Struktur Data : Oleh kerana kita akhirnya mengembalikan indeks, berpegang pada tatasusunan akan berfungsi untuk kita.

Mari .findIndex()lihat untuk melihat bagaimana menyelesaikan masalah ini:

.findIndex()mengembalikan indeks elemen pertama dalam larik yang memenuhi fungsi pengujian yang disediakan. Jika tidak, ia mengembalikan -1, menunjukkan tidak ada elemen yang lulus ujian. Sebagai contoh:

let numbers = [3, 17, 94, 15, 20] numbers.findIndex((currentNum) => currentNum % 2 == 0) // returns 2 numbers.findIndex((currentNum) => currentNum > 100) // returns -1

Ini berguna untuk kita kerana kita dapat menggunakan .findIndex()untuk membandingkan input kita numdengan setiap nombor dalam input kita arrdan mengetahui di mana ia sesuai dalam urutan dari paling sedikit hingga yang paling besar.

Algoritma :

  1. Sekiranya arrarray kosong, kembali 0.
  2. Sekiranya numberada di hujung array yang disusun, kembalikan panjangnya arr.
  3. Otherwise, return the index num would be if arr was sorted from least to greatest.

Code: See below!

function getIndexToIns(arr, num) { // Sort arr from least to greatest. let sortedArray = arr.sort((a, b) => a - b) // [40, 60].sort((a, b) => a - b) // [40, 60] // Compare num to each number in sortedArray // and find the index where num is less than or equal to // a number in sortedArray. let index = sortedArray.findIndex((currentNum) => num  50  falsy // [40, 60].findIndex(60 => 50  truthy // returns 1 because num would fit like so [40, 50, 60] // Return the correct index of num. // If num belongs at the end of sortedArray or if arr is empty // return the length of arr. return index === -1 ? arr.length : index } getIndexToIns([40, 60], 50);

Without local variables and comments:

function getIndexToIns(arr, num) { let index = arr.sort((a, b) => a - b).findIndex((currentNum) => num <= currentNum) return index === -1 ? arr.length : index } getIndexToIns([40, 60], 50);

If you have other solutions and/or suggestions, please share in the comments!

This article is a part of the series freeCodeCamp Algorithm Scripting.

This article references freeCodeCamp Basic Algorithm Scripting: Where do I Belong.

You can follow me on Medium, LinkedIn, and GitHub!