Sådan finder du indekset, hvor et tal hører hjemme i en matrix i JavaScript

Sortering er et meget vigtigt koncept, når man skriver algoritmer. Der er alle mulige slags: boble sorter, skal sorter, blok sorter, kam sorter, cocktail sorter, gnome sorter - jeg gør ikke disse op!

Denne udfordring giver os et indblik i den vidunderlige verden af ​​slags. Vi er nødt til at sortere et array med tal fra mindst til størst og finde ud af, hvor et givet nummer vil høre hjemme i det array.

Algoritme instruktioner

Returner det laveste indeks, hvor en værdi (andet argument) skal indsættes i en matrix (første argument), når den er sorteret. Den returnerede værdi skal være et tal. For eksempel getIndexToIns([1,2,3,4], 1.5)skal den returnere, 1fordi den er større end 1(indeks 0), men mindre end 2(indeks 1). Ligeledes getIndexToIns([20,3,5], 19)skal den returnere, 2fordi når matrixen er sorteret, ser den ud [3,5,20]og 19er mindre end 20(indeks 2) og større end 5(indeks 1).
function getIndexToIns(arr, num) { return num; } getIndexToIns([40, 60], 50);

Medfølgende testtilfælde

  • getIndexToIns([10, 20, 30, 40, 50], 35)skulle vende tilbage 3.
  • getIndexToIns([10, 20, 30, 40, 50], 35) skal returnere et nummer.
  • getIndexToIns([10, 20, 30, 40, 50], 30)skulle vende tilbage 2.
  • getIndexToIns([10, 20, 30, 40, 50], 30) skal returnere et nummer.
  • getIndexToIns([40, 60], 50)skulle vende tilbage 1.
  • getIndexToIns([40, 60], 50) skal returnere et nummer.
  • getIndexToIns([3, 10, 5], 3)skulle vende tilbage 0.
  • getIndexToIns([3, 10, 5], 3) skal returnere et nummer.
  • getIndexToIns([5, 3, 20, 3], 5)skulle vende tilbage 2.
  • getIndexToIns([5, 3, 20, 3], 5) skal returnere et nummer.
  • getIndexToIns([2, 20, 10], 19)skulle vende tilbage 2.
  • getIndexToIns([2, 20, 10], 19) skal returnere et nummer.
  • getIndexToIns([2, 5, 10], 15)skulle vende tilbage 3.
  • getIndexToIns([2, 5, 10], 15) skal returnere et nummer.
  • getIndexToIns([], 1)skulle vende tilbage 0.
  • getIndexToIns([], 1) skal returnere et nummer.

Løsning nr. 1: .sort (), .indexOf ()

PEDAC

Forståelse af problemet : Vi har to indgange, et array og et tal. Vores mål er at returnere indekset for vores inputnummer, efter at det er sorteret i input-arrayet.

Eksempler / testtilfælde: De gode mennesker på freeCodeCamp fortæller os ikke, på hvilken måde input-arrayet skal sorteres, men de medfølgende testcases gør det klart, at input-arrayet skal sorteres fra mindst til størst.

Bemærk, at der er en kantsag på de sidste to leverede testtilfælde, hvor inputmatrixen er en tom matrix.

Datastruktur : Da vi i sidste ende returnerer et indeks, vil det holde fast ved arrays fungere for os.

Vi skal bruge en smidig metode ved navn .indexOf():

.indexOf()returnerer det første indeks, hvor et element er til stede i en matrix, eller a -1hvis elementet overhovedet ikke er til stede. For eksempel:

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

Vi bruger også .concat()her i stedet for .push(). Hvorfor? Fordi når du føjer et element til et array ved hjælp af .push()det, returnerer det længden af ​​det nye array. Når du føjer et element til et array ved hjælp af .concat()det, returnerer det det nye array selv. For eksempel:

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

Algoritme :

  1. Indsæt numi arr.
  2. Sorter arrfra mindst til størst.
  3. Returner indekset for num.

Kode : Se nedenfor!

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

Uden lokale variabler og kommentarer:

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

Løsning nr. 2: .sort (), .findIndex ()

PEDAC

Forståelse af problemet : Vi har to indgange, et array og et tal. Vores mål er at returnere indekset for vores inputnummer, efter at det er sorteret i input-arrayet.

Eksempler / testtilfælde: De gode mennesker på freeCodeCamp fortæller os ikke, på hvilken måde input-arrayet skal sorteres, men de medfølgende testcases gør det klart, at input-arrayet skal sorteres fra mindst til størst.

Der er to kantsager, der skal tages i betragtning med denne løsning:

  1. Hvis input-arrayet er tom, er vi nødt til at vende tilbage, 0fordi det numville være det eneste element i denne array, derfor ved indeks 0.
  2. Hvis numville høre hjemme i slutningen af arrsorteret fra mindst til størst, er vi nødt til at returnere længden af arr.

Datastruktur : Da vi i sidste ende returnerer et indeks, vil det holde fast ved arrays fungere for os.

Lad os tjekke for .findIndex()at se, hvordan det hjælper med at løse denne udfordring:

.findIndex()returnerer indekset for det første element i arrayet, der opfylder den leverede testfunktion. Ellers returnerer den -1, hvilket indikerer, at intet element har bestået testen. For eksempel:

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

Dette er nyttigt for os, fordi vi kan bruge .findIndex()til at sammenligne vores input nummed hvert nummer i vores input arrog finde ud af, hvor det passer i rækkefølge fra mindst til størst.

Algoritme :

  1. Hvis arrer et tomt array, skal du returnere 0.
  2. Hvis numhører hjemme i slutningen af ​​det sorterede array, skal du returnere længden af arr.
  3. Ellers numville indekset vende tilbage, hvis det arrblev sorteret fra mindst til størst.

Kode : Se nedenfor!

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

Uden lokale variabler og kommentarer:

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

Hvis du har andre løsninger og / eller forslag, bedes du dele i kommentarerne!

Denne artikel er en del af serien freeCodeCamp Algorithm Scripting.

Denne artikel henviser til freeCodeCamp Basic Algorithm Scripting: Hvor tilhører jeg.

Du kan følge mig på Medium, LinkedIn og GitHub!