Как да намерим индекса, където дадено число принадлежи в масив в JavaScript

Сортирането е много важна концепция при писане на алгоритми. Има всякакви видове: сортиране на балончета, сортиране на черупки, сортиране на блокове, сортиране на гребени, сортиране на коктейли, сортиране на гном - не ги измислям!

Това предизвикателство ни дава поглед към чудесния свят. Трябва да сортираме масив от числа от най-малкото до най-голямото и да разберем къде дадено число би принадлежало в този масив.

Инструкции за алгоритъма

Връща най-ниския индекс, при който стойност (втори аргумент) трябва да бъде вмъкната в масив (първи аргумент), след като е сортирана. Върнатата стойност трябва да е число. Например 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 ()

ПЕДАК

Разбиране на проблема : Имаме два входа, масив и число. Нашата цел е да върнем индекса на нашия входен номер, след като той бъде сортиран във входния масив.

Примери / тестови случаи : Добрите хора в 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);

Ако имате други решения и / или предложения, моля, споделете в коментарите!

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!