Kuinka löytää hakemisto, jossa numero kuuluu matriisiin JavaScriptissä

Lajittelu on erittäin tärkeä käsite algoritmeja kirjoitettaessa. On olemassa kaikenlaisia: kuplalajittelu, kuorilajittelu, lohkolajittelu, kampa-lajittelu, cocktail-lajittelu, tonttu-lajittelu - en tee näitä!

Tämä haaste antaa meille vilauksen eräänlaiseen upeaan maailmaan. Meidän on lajiteltava joukko numeroita pienimmistä suurimpiin ja selvitettävä, mihin tietty numero kuuluisi.

Algoritmin ohjeet

Palauttaa pienimmän indeksin, jolla arvo (toinen argumentti) tulisi lisätä taulukkoon (ensimmäinen argumentti), kun se on lajiteltu. Palautettavan arvon on oltava luku, esimerkiksi getIndexToIns([1,2,3,4], 1.5)palautettava, 1koska se on suurempi kuin 1(indeksi 0), mutta pienempi kuin 2(indeksi 1). Samoin getIndexToIns([20,3,5], 19)pitäisi palata, 2koska kun taulukko on lajiteltu, se näyttää [3,5,20]ja 19on pienempi kuin 20(indeksi 2) ja suurempi kuin 5(indeksi 1).
function getIndexToIns(arr, num) { return num; } getIndexToIns([40, 60], 50);

Toimitetut testitapaukset

  • getIndexToIns([10, 20, 30, 40, 50], 35)pitäisi palata 3.
  • getIndexToIns([10, 20, 30, 40, 50], 35) pitäisi palauttaa numero.
  • getIndexToIns([10, 20, 30, 40, 50], 30)pitäisi palata 2.
  • getIndexToIns([10, 20, 30, 40, 50], 30) pitäisi palauttaa numero.
  • getIndexToIns([40, 60], 50)pitäisi palata 1.
  • getIndexToIns([40, 60], 50) pitäisi palauttaa numero.
  • getIndexToIns([3, 10, 5], 3)pitäisi palata 0.
  • getIndexToIns([3, 10, 5], 3) pitäisi palauttaa numero.
  • getIndexToIns([5, 3, 20, 3], 5)pitäisi palata 2.
  • getIndexToIns([5, 3, 20, 3], 5) pitäisi palauttaa numero.
  • getIndexToIns([2, 20, 10], 19)pitäisi palata 2.
  • getIndexToIns([2, 20, 10], 19) pitäisi palauttaa numero.
  • getIndexToIns([2, 5, 10], 15)pitäisi palata 3.
  • getIndexToIns([2, 5, 10], 15) pitäisi palauttaa numero.
  • getIndexToIns([], 1)pitäisi palata 0.
  • getIndexToIns([], 1) pitäisi palauttaa numero.

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

PEDAC

Ongelman ymmärtäminen : Meillä on kaksi tuloa, taulukko ja luku. Tavoitteenamme on palauttaa syötetyn numeromme hakemisto sen jälkeen, kun se on lajiteltu syötetaulukkoon.

Esimerkit / testitapaukset : FreeCodeCampin hyvät ihmiset eivät kerro meille, millä tavalla tuloryhmä tulisi lajitella, mutta toimitetut testitapaukset tekevät selväksi, että syötetaulukko on lajiteltava vähiten suurimpaan.

Huomaa, että kahdessa viimeksi toimitetussa testitapauksessa on reunatapa, jossa syötetaulukko on tyhjä taulukko.

Tietorakenne : Koska palautamme viime kädessä indeksin, matriisien kiinnittäminen toimii meille.

Aiomme käyttää hienoa menetelmää nimeltä .indexOf():

.indexOf()palauttaa ensimmäisen indeksin, jolla elementti on matriisissa, tai a, -1jos elementtiä ei ole ollenkaan. Esimerkiksi:

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

Aiomme käyttää myös .concat()täällä .push(). Miksi? Koska kun lisäät elementin matriisiin käyttämällä .push(), se palauttaa uuden matriisin pituuden. Kun lisäät elementin matriisiin käyttämällä .concat(), se palauttaa uuden taulukon itse. Esimerkiksi:

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

Algoritmi :

  1. Aseta numosaksi arr.
  2. Lajittele arrvähiten suurimpaan.
  3. Palauttaa hakemiston num.

Koodi : Katso alla!

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

Ilman paikallisia muuttujia ja kommentteja:

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

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

PEDAC

Ongelman ymmärtäminen : Meillä on kaksi tuloa, taulukko ja luku. Tavoitteenamme on palauttaa syötetyn numeromme hakemisto sen jälkeen, kun se on lajiteltu syötetaulukkoon.

Esimerkit / testitapaukset : FreeCodeCampin hyvät ihmiset eivät kerro meille, millä tavalla tuloryhmä tulisi lajitella, mutta toimitetut testitapaukset tekevät selväksi, että syötetaulukko on lajiteltava vähiten suurimpaan.

Tässä ratkaisussa on otettava huomioon kaksi reunatapausta:

  1. Jos syöttötaulukko on tyhjä, meidän on palattava, 0koska numse olisi ainoa elementti siinä taulukossa, siis indeksissä 0.
  2. Jos numse kuuluisi arrlajiteltuun loppupäähän pienimmistä suurimpiin, meidän on palautettava pituuden arvo arr.

Tietorakenne : Koska palautamme viime kädessä indeksin, matriisien kiinnittäminen toimii meille.

Katsotaanpa, .findIndex()miten se auttaa ratkaisemaan tämän haasteen:

.findIndex()palauttaa taulukon ensimmäisen elementin indeksin, joka täyttää tarjotun testaustoiminnon. Muussa tapauksessa se palauttaa -1, mikä tarkoittaa, ettei yksikään elementti läpäissyt testiä. Esimerkiksi:

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

Tästä on hyötyä meille, koska voimme .findIndex()verrata syötettämme numjokaiseen syötteemme numeroon arrja selvittää missä se sopisi järjestyksessä vähiten suurimpaan.

Algoritmi :

  1. Jos arrtaulukko on tyhjä, palaa 0.
  2. Jos numkuuluu lopussa lajitellun array, palauta pituutta arr.
  3. Muussa tapauksessa indeksi palautetaan, numjos arrse lajitellaan vähimmäisarvosta suurimpaan.

Koodi : Katso alla!

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

Ilman paikallisia muuttujia ja kommentteja:

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

Jos sinulla on muita ratkaisuja ja / tai ehdotuksia, jaa kommenteissa!

Tämä artikkeli on osa sarjan freeCodeCamp Algorithm Scripting -sarjaa.

Tässä artikkelissa viitataan freeCodeCamp Basic Algorithm Scripting: Minne kuulun.

Voit seurata minua Mediumissa, LinkedInissä ja GitHubissa!