كيفية العثور على الفهرس الذي ينتمي إليه الرقم في مصفوفة في JavaScript

يعتبر الفرز مفهومًا مهمًا جدًا عند كتابة الخوارزميات. هناك كل أنواع الأنواع: نوع الفقاعة ، نوع القشرة ، نوع الكتلة ، نوع المشط ، نوع الكوكتيل ، نوع جنوم - أنا لا أقوم بصنعها!

يعطينا هذا التحدي لمحة عن عالم رائع من نوع ما. علينا فرز مصفوفة من الأعداد من الأصغر إلى الأكبر ومعرفة أين ينتمي عدد معين في تلك المصفوفة.

تعليمات الخوارزمية

قم بإرجاع أدنى فهرس حيث يجب إدراج قيمة (الوسيطة الثانية) في مصفوفة (الوسيطة الأولى) بمجرد فرزها. يجب أن تكون القيمة التي تم إرجاعها مثال number.For، getIndexToIns([1,2,3,4], 1.5)يجب أن تعود 1لأنها أكبر من 1(فهرس 0)، ولكن أقل من 2(فهرس 1) .Likewise، 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 ()

بيداك

فهم المشكلة : لدينا مدخلين ، مصفوفة ورقم. هدفنا هو إرجاع فهرس رقم الإدخال الخاص بنا بعد أن يتم فرزه في مصفوفة الإدخال.

أمثلة / حالات اختبار : لا يخبرنا الأشخاص الطيبون في 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 ()

بيداك

فهم المشكلة : لدينا مدخلين ، مصفوفة ورقم. هدفنا هو إرجاع فهرس رقم الإدخال الخاص بنا بعد أن يتم فرزه في مصفوفة الإدخال.

أمثلة / حالات اختبار : لا يخبرنا الأشخاص الطيبون في 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 الأساسية: أين أنتمي.

يمكنك متابعتي على Medium و LinkedIn و GitHub!