Сортировка - очень важная концепция при написании алгоритмов. Есть все виды сортировки: пузырьковая сортировка, сортировка ракушкой, сортировка блоков, сортировка гребней, сортировка коктейлей, сортировка гномов - Я не придумываю это!

Этот вызов дает нам возможность заглянуть в своего рода чудесный мир. Мы должны отсортировать массив чисел от наименьшего к наибольшему и выяснить, где данное число будет принадлежать этому массиву.

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

Возвращает наименьший индекс, по которому значение (второй аргумент) должно быть вставлено в массив (первый аргумент) после его сортировки. Возвращаемое значение должно быть числом.

Например, 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).

Предоставленные тестовые случаи

  • 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 2
food.indexOf('spaghetti')
// returns -1

Мы также собираемся использовать здесь .concat() вместо .push(). Почему? Потому что, когда вы добавляете элемент в массив с помощью .push(), он возвращает длину нового массива. Когда вы добавляете элемент в массив с помощью .concat(), он возвращает сам новый массив. Например:

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

Алгоритм:

  1. Вставьте num в arr.
  2. Сортируйте arr от наименьшего к наибольшему.
  3. Вернуть индекс num.

Код: см. ниже!

Без локальных переменных и комментариев:

Решение # 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 был отсортирован от наименьшего к наибольшему.

Код: см. ниже!

Без локальных переменных и комментариев:

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

Эта статья является частью серии Создание скриптов алгоритмов freeCodeCamp.

Эта статья ссылается на Сценарии базового алгоритма freeCodeCamp: к чему я принадлежу.

Вы можете подписаться на меня на Medium, LinkedIn и GitHub!