Добро пожаловать в раздел Разгадывание математических загадок с помощью JavaScript. JavaScript — один из самых популярных и высокооплачиваемых языков программирования в наши дни. Это также один из самых простых языков программирования для написания кода.
Мы решили опубликовать серию статей о задачах по математике и о том, как их решать с помощью JavaScript.
Прежде чем мы начнем, вот несколько предварительных условий:
- Вы должны быть знакомы с JavaScript, OOJS и ES2015 и выше.
- Вы должны быть знакомы со структурами данных и алгоритмами.
Достаточно сказано! Давайте начнем…
Найти наименьший элемент в отсортированном повернутом массиве
Прежде чем мы начнем, давайте разберемся, что такое повернутый массив. Предположим, есть список чисел 1, 2, 3, 4 и 5. Если я поверну этот список на позицию 2 для данного массива, список станет [5, 1, 2, 3, 4]. Если я поверну список на позицию 4, он по существу станет [2, 3, 4, 5, 1]. Как найти наименьший элемент
(или n-й наименьший элемент) в таком массиве?
Ответ прост: найдите элемент, чей предыдущий родственный элемент больше по значению. Но прежде чем мы перейдем к решению, давайте рассмотрим простое решение JavaScript с использованием методов встроенной библиотеки.
Решение 1. Прямолинейный подход
function findSmallest(arr = []) { const smallest = arr.find((el, index) => arr[index - 1] > el); if (smallest === undefined) return arr[0]; // First element return smallest; }
Метод массива find
возвращает первый элемент, соответствующий заданному условию. Теперь давайте настроим эту реализацию, чтобы найти n-й наименьший элемент.
function findNthSmallest(arr = [], n = 0) { let smallest = arr.find((el, index) => arr[index - 1] > el); if (smallest === undefined) { smallest = arr[0]; // First element } if (n === 0) return smallest; let nthIndex = arr.indexOf(smallest) + n; if (nthIndex >= arr.length) { nthIndex -= arr.length; // Since array is rotated } return arr[nthIndex] > smallest ? arr[nthIndex] : undefined; }
Хорошо! Это было простое решение для JavaScript. Очевидно, что ваш интервьюер может искать решение, не использующее встроенные методы. Следующее решение, которое мы собираемся исследовать, включает рекурсивное решение с использованием бинарного поиска.
Решение 2. Решение для двоичного поиска
Принцип работы бинарного поиска довольно прост. Мы разделяем массив из середины и сравниваем левый и правый элементы с текущим элементом. Если левый элемент меньше текущего, мы рассматриваем все крайние левые элементы как отдельный массив и запускаем для них бинарный поиск. То же самое повторяется для правого элемента. Единственное, о чем нам нужно позаботиться, это в каком направлении нам нужно идти. Остальная логика поиска n-го наименьшего элемента остается такой же, как и выше. Нам нужно найти наименьший элемент. Вот решение для этого.
function smallest(arr = [], low, high) { if (low > high) return arr[0]; if (low === high) return arr[low]; const mid = Math.floor((low + high) / 2); if (mid < high && arr[mid] > arr[mid + 1]) { return arr[mid + 1]; } if (mid > low && arr[mid] < arr[mid - 1]) { return arr[mid]; } if (arr[high] > arr[mid]) { // go left return smallest(arr, low, mid - 1); } // else go right (since it's rotated) return smallest(arr, mid + 1, high); } function nthSmallest(arr = [], n = 0) { const small = smallest(arr, 0, arr.length - 1); if (n === 0) return small; let nthIndex = arr.indexOf(small) + n; if (nthIndex >= arr.length) { nthIndex -= arr.length; // Since array is rotated } return arr[nthIndex] > small ? arr[nthIndex] : undefined; }
Ну вот!
Пожалуйста, оставьте комментарий ниже, если у вас есть другое решение, или просто какой-то общий отзыв. Спасибо за чтение!