A rendezés nagyon fontos fogalom algoritmusok írásakor. Mindenféle létezik: buborék-rendezés, héj-rendezés, blokk-rendezés, fésű-rendezés, koktél-rendezés, gnóm-rendezés - ezeket nem kitalálom!
Ez a kihívás bepillantást enged a fajta csodálatos világába. A számok tömbjét a legkevesebbtől a legnagyobbig kell rendezni, és meg kell derítenünk, hogy egy adott szám hova tartozna abban a tömbben.
Algoritmus utasítások
Visszaadja azt a legkisebb indexet, amelynél egy értéket (második argumentum) be kell illeszteni egy tömbbe (első argumentum), miután rendezte. A visszaadott értéknek számnak kell lennie. PéldáulgetIndexToIns([1,2,3,4], 1.5)
vissza kell térnie,
1
mert nagyobb, mint
1
(index 0), de kisebb, mint
2
(index 1). Hasonlóképpen,
getIndexToIns([20,3,5], 19)
vissza kell térnie,
2
mert a tömb rendezése után kinézni fog,
[3,5,20]
és
19
kisebb, mint
20
(2. index) és nagyobb, mint
5
(1. index).
function getIndexToIns(arr, num) { return num; } getIndexToIns([40, 60], 50);
Biztosított tesztesetek
getIndexToIns([10, 20, 30, 40, 50], 35)
vissza kell térnie3
.getIndexToIns([10, 20, 30, 40, 50], 35)
számot kell visszaadnia.getIndexToIns([10, 20, 30, 40, 50], 30)
vissza kell térnie2
.getIndexToIns([10, 20, 30, 40, 50], 30)
számot kell visszaadnia.getIndexToIns([40, 60], 50)
vissza kell térnie1
.getIndexToIns([40, 60], 50)
számot kell visszaadnia.getIndexToIns([3, 10, 5], 3)
vissza kell térnie0
.getIndexToIns([3, 10, 5], 3)
számot kell visszaadnia.getIndexToIns([5, 3, 20, 3], 5)
vissza kell térnie2
.getIndexToIns([5, 3, 20, 3], 5)
számot kell visszaadnia.getIndexToIns([2, 20, 10], 19)
vissza kell térnie2
.getIndexToIns([2, 20, 10], 19)
számot kell visszaadnia.getIndexToIns([2, 5, 10], 15)
vissza kell térnie3
.getIndexToIns([2, 5, 10], 15)
számot kell visszaadnia.getIndexToIns([], 1)
vissza kell térnie0
.getIndexToIns([], 1)
számot kell visszaadnia.
1. megoldás: .sort (), .indexOf ()
PEDAC
A probléma megértése : Két bemenetünk van, egy tömb és egy szám. Célunk, hogy a bemeneti tömbbe rendezés után visszaadjuk a bemeneti számunk indexét.
Példák / tesztesetek : A freeCodeCamp jó emberei nem mondják meg nekünk, hogy a bemeneti tömböt milyen módon kell rendezni, de a megadott tesztesetek egyértelművé teszik, hogy a bemeneti tömböt a legkevesebbtől a legnagyobbig kell rendezni.
Figyelje meg, hogy a legutóbbi két tesztesetben van egy éles eset, amikor a bemeneti tömb üres tömb.
Adatszerkezet : Mivel végül egy indexet adunk vissza, a tömbökkel való ragaszkodás számunkra beválik.
Egy remek módszert fogunk használni .indexOf()
:
.indexOf()
az első indexet adja meg, amelynél egy elem jelen van egy tömbben, vagy egy, -1
ha az elem egyáltalán nincs jelen. Például:
let food = ['pizza', 'ice cream', 'chips', 'hot dog', 'cake']
food.indexOf('chips')// returns 2food.indexOf('spaghetti')// returns -1
Mi is itt fogunk használni .concat()
helyett .push()
. Miért? Mert amikor egy elemet hozzáad egy tömbhöz .push()
, az visszaadja az új tömb hosszát. Ha egy elemet hozzáad egy tömbhöz .concat()
, akkor maga adja vissza az új tömböt. Például:
let array = [4, 10, 20, 37, 45]
array.push(98)// returns 6array.concat(98)// returns [4, 10, 20, 37, 45, 98]
Algoritmus :
- Helyezze
num
bearr
. - Rendezés
arr
a legkevesebbtől a legnagyobbig. - Adja vissza a
num
.
Kód : Lásd alább!
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);
Helyi változók és megjegyzések nélkül:
function getIndexToIns(arr, num) { return arr.concat(num).sort((a, b) => a - b).indexOf(num); } getIndexToIns([40, 60], 50);
2. megoldás: .sort (), .findIndex ()
PEDAC
A probléma megértése : Két bemenetünk van, egy tömb és egy szám. Célunk, hogy a bemeneti tömbbe rendezés után visszaadjuk a bemeneti számunk indexét.
Példák / tesztesetek : A freeCodeCamp jó emberei nem mondják meg nekünk, hogy a bemeneti tömböt milyen módon kell rendezni, de a megadott tesztesetek egyértelművé teszik, hogy a bemeneti tömböt a legkevesebbtől a legnagyobbig kell rendezni.
Két megoldásnál figyelembe kell venni a megoldást:
- Ha a bemeneti tömb üres, akkor vissza kell térnünk,
0
mertnum
ez lenne az egyetlen elem a tömbben, tehát az indexen0
. - Ha a legkésőbbiektől a legnagyobbakig
num
aarr
rendezés legvégére tartozna , akkor vissza kell adnunk a hosszátarr
.
Adatszerkezet : Mivel végül egy indexet adunk vissza, a tömbökkel való ragaszkodás számunkra beválik.
Nézzük meg a pénztárat, .findIndex()
és nézzük meg, hogyan segít megoldani ezt a kihívást:
.findIndex()
a tömb első elemének indexét adja vissza, amely megfelel a megadott tesztfunkciónak. Ellenkező esetben -1 értéket ad vissza, jelezve, hogy egyetlen elem sem ment át a teszten. Például:
let numbers = [3, 17, 94, 15, 20] numbers.findIndex((currentNum) => currentNum % 2 == 0) // returns 2 numbers.findIndex((currentNum) => currentNum > 100) // returns -1
Ez azért hasznos számunkra, mert .findIndex()
a bemenetünket összehasonlíthatjuk a bemenetünk num
minden számával, arr
és kitalálhatjuk, hogy hol illene a legkevésbé a legnagyobbra.
Algoritmus :
- Ha
arr
üres tömb, akkor térjen vissza0
. - Ha
num
a rendezett tömb végébe tartozik, adja vissza a hosszátarr
. - Otherwise, return the index
num
would be ifarr
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!