Πώς να βρείτε το ευρετήριο όπου ένας αριθμός ανήκει σε έναν πίνακα σε JavaScript

Η ταξινόμηση είναι μια πολύ σημαντική έννοια κατά τη σύνταξη αλγορίθμων. Υπάρχουν όλα τα είδη των ειδών: είδος φούσκα, είδος κελύφους, είδος μπλοκ, είδος χτένας, είδος κοκτέιλ, είδος gnome - δεν τα κάνω!

Αυτή η πρόκληση μας δίνει μια ματιά στον υπέροχο κόσμο των ειδών. Πρέπει να ταξινομήσουμε έναν πίνακα αριθμών από το λιγότερο στο μεγαλύτερο και να μάθουμε πού θα ανήκε ένας συγκεκριμένος αριθμός σε αυτόν τον πίνακα.

Οδηγίες αλγορίθμου

Επιστρέψτε το χαμηλότερο ευρετήριο στον οποίο μια τιμή (δεύτερο όρισμα) πρέπει να εισαχθεί σε έναν πίνακα (πρώτο όρισμα) μόλις ταξινομηθεί. Η επιστρεφόμενη τιμή πρέπει να είναι αριθμός. Για παράδειγμα, getIndexToIns([1,2,3,4], 1.5)πρέπει να επιστρέψει 1επειδή είναι μεγαλύτερη από 1(ευρετήριο 0), αλλά μικρότερη από 2(ευρετήριο 1). Ομοίως, getIndexToIns([20,3,5], 19)θα πρέπει να επιστρέψει 2επειδή μόλις ταξινομηθεί ο πίνακας θα μοιάζει [3,5,20]και 19είναι μικρότερος από 20(ευρετήριο 2) και μεγαλύτερο από 5(δείκτης 1).
function getIndexToIns(arr, num) { return num; } getIndexToIns([40, 60], 50);

Παρεχόμενες δοκιμές

  • getIndexToIns([10, 20, 30, 40, 50], 35)πρέπει να επιστρέψει 3.
  • getIndexToIns([10, 20, 30, 40, 50], 35) πρέπει να επιστρέψει έναν αριθμό.
  • getIndexToIns([10, 20, 30, 40, 50], 30)πρέπει να επιστρέψει 2.
  • getIndexToIns([10, 20, 30, 40, 50], 30) πρέπει να επιστρέψει έναν αριθμό.
  • getIndexToIns([40, 60], 50)πρέπει να επιστρέψει 1.
  • getIndexToIns([40, 60], 50) πρέπει να επιστρέψει έναν αριθμό.
  • getIndexToIns([3, 10, 5], 3)πρέπει να επιστρέψει 0.
  • getIndexToIns([3, 10, 5], 3) πρέπει να επιστρέψει έναν αριθμό.
  • getIndexToIns([5, 3, 20, 3], 5)πρέπει να επιστρέψει 2.
  • getIndexToIns([5, 3, 20, 3], 5) πρέπει να επιστρέψει έναν αριθμό.
  • getIndexToIns([2, 20, 10], 19)πρέπει να επιστρέψει 2.
  • getIndexToIns([2, 20, 10], 19) πρέπει να επιστρέψει έναν αριθμό.
  • getIndexToIns([2, 5, 10], 15)πρέπει να επιστρέψει 3.
  • getIndexToIns([2, 5, 10], 15) πρέπει να επιστρέψει έναν αριθμό.
  • getIndexToIns([], 1)πρέπει να επιστρέψει 0.
  • getIndexToIns([], 1) πρέπει να επιστρέψει έναν αριθμό.

Λύση # 1: .sort (), .indexOf ()

PEDAC

Κατανόηση του προβλήματος : Έχουμε δύο εισόδους, έναν πίνακα και έναν αριθμό. Στόχος μας είναι να επιστρέψουμε το ευρετήριο του αριθμού εισόδου μας αφού ταξινομηθεί στον πίνακα εισαγωγής.

Παραδείγματα / Περίπτωση δοκιμής : Οι καλοί άνθρωποι στο freeCodeCamp δεν μας λένε με ποιον τρόπο θα πρέπει να ταξινομηθεί ο πίνακας εισόδου, αλλά οι παρεχόμενες δοκιμαστικές περιπτώσεις καθιστούν σαφές ότι ο πίνακας εισόδου πρέπει να ταξινομηθεί από το λιγότερο στο μεγαλύτερο.

Παρατηρήστε ότι υπάρχει ένα περίβλημα στις δύο τελευταίες δοκιμαστικές περιπτώσεις όπου ο πίνακας εισόδου είναι ένας κενός πίνακας.

Δομή δεδομένων : Δεδομένου ότι τελικά επιστρέφουμε ένα ευρετήριο, το να κολλήσουμε με πίνακες θα λειτουργήσει για εμάς.

Θα χρησιμοποιήσουμε μια ωραία μέθοδο που ονομάζεται .indexOf():

.indexOf()επιστρέφει το πρώτο ευρετήριο στο οποίο ένα στοιχείο υπάρχει σε έναν πίνακα, ή -1εάν το στοιχείο δεν υπάρχει καθόλου Για παράδειγμα:

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

Θα χρησιμοποιούμε επίσης .concat()εδώ αντί για .push(). Γιατί; Επειδή όταν προσθέτετε ένα στοιχείο σε έναν πίνακα χρησιμοποιώντας .push(), επιστρέφει το μήκος του νέου πίνακα. Όταν προσθέτετε ένα στοιχείο σε έναν πίνακα χρησιμοποιώντας .concat(), επιστρέφει τον ίδιο τον νέο πίνακα. Για παράδειγμα:

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

Αλγόριθμος :

  1. Εισαγωγή numσε arr.
  2. Ταξινόμηση arrαπό το λιγότερο στο μεγαλύτερο.
  3. Επιστρέψτε το ευρετήριο του num.

Κωδικός : Δείτε παρακάτω!

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

Χωρίς τοπικές μεταβλητές και σχόλια:

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

Λύση # 2: .sort (), .findIndex ()

PEDAC

Κατανόηση του προβλήματος : Έχουμε δύο εισόδους, έναν πίνακα και έναν αριθμό. Στόχος μας είναι να επιστρέψουμε το ευρετήριο του αριθμού εισόδου μας αφού ταξινομηθεί στον πίνακα εισαγωγής.

Παραδείγματα / Περίπτωση δοκιμής : Οι καλοί άνθρωποι στο freeCodeCamp δεν μας λένε με ποιον τρόπο θα πρέπει να ταξινομηθεί ο πίνακας εισόδου, αλλά οι παρεχόμενες δοκιμαστικές περιπτώσεις καθιστούν σαφές ότι ο πίνακας εισόδου πρέπει να ταξινομηθεί από το λιγότερο στο μεγαλύτερο.

Υπάρχουν δύο ακραίες περιπτώσεις που πρέπει να ληφθούν υπόψη με αυτήν τη λύση:

  1. Εάν ο πίνακας εισόδου είναι κενός, τότε πρέπει να επιστρέψουμε 0γιατί numθα ήταν το μόνο στοιχείο σε αυτόν τον πίνακα, επομένως στο ευρετήριο 0.
  2. Εάν numανήκε στο τέλος της arrταξινόμησης από το λιγότερο στο μεγαλύτερο, τότε πρέπει να επιστρέψουμε το μήκος του arr.

Δομή δεδομένων : Δεδομένου ότι τελικά επιστρέφουμε ένα ευρετήριο, το να κολλήσουμε με πίνακες θα λειτουργήσει για εμάς.

Ας ρίξουμε μια ματιά .findIndex()για να δούμε πώς θα βοηθήσει στην επίλυση αυτής της πρόκλησης:

.findIndex()επιστρέφει το ευρετήριο του πρώτου στοιχείου στον πίνακα που ικανοποιεί την παρεχόμενη συνάρτηση δοκιμής. Διαφορετικά, επιστρέφει -1, δείχνοντας ότι κανένα στοιχείο δεν πέρασε το τεστ. Για παράδειγμα:

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

Αυτό είναι χρήσιμο για εμάς γιατί μπορούμε να χρησιμοποιήσουμε .findIndex()για να συγκρίνουμε τις εισόδους μας numμε κάθε αριθμό στην είσοδο μας arrκαι να καταλάβουμε πού θα ταιριάζει με τη σειρά από το λιγότερο στο μεγαλύτερο.

Αλγόριθμος :

  1. Εάν arrείναι κενός πίνακας, επιστρέψτε 0.
  2. Εάν numανήκει στο τέλος του ταξινομημένου πίνακα, επιστρέψτε το μήκος του arr.
  3. Διαφορετικά, επιστρέψτε το ευρετήριο numθα ήταν εάν arrταξινομήθηκε από το λιγότερο στο μεγαλύτερο.

Κωδικός : Δείτε παρακάτω!

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

Χωρίς τοπικές μεταβλητές και σχόλια:

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

Εάν έχετε άλλες λύσεις ή / και προτάσεις, μοιραστείτε τα σχόλια!

Αυτό το άρθρο είναι μέρος της σειράς FreeCodeCamp Algorithm Scripting.

Αυτό το άρθρο αναφέρεται σε σενάριο freeCodeCamp Basic Algorithm Scripting: Where I Belong.

Μπορείτε να με ακολουθήσετε στο Medium, το LinkedIn και το GitHub!