Давайте найдем недостающие числа в массивах, используя сравнение или математические подходы. Избегайте распространенных заблуждений
В мире программирования решение головоломок и задач является важной частью оттачивания наших навыков решения проблем. Одна из таких интригующих головоломок — найти пропущенное число в массиве последовательных целых чисел. Эта проблема может показаться простой на первый взгляд, но она может быстро стать сложной, если вы не знаете о некоторых распространенных заблуждениях. В этой статье мы рассмотрим постановку задачи, предоставим фрагменты кода JavaScript для ее решения с использованием как подхода сравнения, так и математического подхода, а также обсудим некоторые неправильные представления, на которые следует обратить внимание. Давайте погрузимся!
Постановка задачи:
Дан массив последовательных целых чисел, нам нужно найти пропущенное число. Массив будет иметь размер n, содержащий целые числа от 1 до n+1. В массиве будет отсутствовать только одно число из этого диапазона. Наша задача — эффективно определить недостающее число.
Сравнительный подход:
Ниже приведена функция JavaScript, которая решает проблему пропущенного числа, используя подход сравнения:
function findMissingNumberComparison(arr) { const n = arr.length + 1; let missingNumber = 0; for (let i = 1; i <= n; i++) { if (!arr.includes(i)) { missingNumber = i; break; } } return missingNumber; }
- Функция
findMissingNumberComparison
принимает на вход массивarr
. - Мы инициализируем переменную
missingNumber
значением 0. - Используя цикл
for
, мы итерируем от 1 до n (включительно), поскольку отсутствующее число может находиться в диапазоне от 1 до n+1. - Внутри цикла мы проверяем наличие текущего числа в массиве с помощью метода
includes
. - Если число не найдено в массиве, это означает, что это отсутствующее число. Мы присваиваем его переменной
missingNumber
и выходим из цикла. - Наконец, мы возвращаем недостающее число в качестве вывода функции.
Математический подход:
Теперь давайте рассмотрим более эффективный математический подход к решению проблемы пропущенного числа:
function findMissingNumberMath(arr) { const n = arr.length + 1; const sum = (n * (n + 1)) / 2; const actualSum = arr.reduce((acc, curr) => acc + curr, 0); return sum - actualSum; }
- Функция
findMissingNumberMath
принимает на вход массивarr
. - Мы вычисляем ожидаемую сумму последовательных чисел в диапазоне (от 1 до n+1) по формуле
(n * (n + 1)) / 2
, где n — длина входного массива плюс один. - Затем мы вычисляем фактическую сумму элементов в массиве, используя функцию
reduce
, которая выполняет итерацию по каждому элементу и накапливает их сумму. - Недостающее число можно найти, вычитая фактическую сумму из ожидаемой суммы.
- Наконец, мы возвращаем недостающее число в качестве вывода функции.
Пример набора данных и выполнения:
Давайте рассмотрим массив [1, 2, 3, 5, 6]
в качестве нашего примера набора данных. Ожидаемый результат должен быть 4, поскольку это отсутствующее число в данном массиве.
const arr = [1, 2, 3, 5, 6]; const missingNumberComparison = findMissingNumberComparison(arr); const missingNumberMath = findMissingNumberMath(arr); console.log("Comparison Approach: ", missingNumberComparison); // Output: 4 console.log("Mathematical Approach: ", missingNumberMath); // Output: 4
Распространенные заблуждения:
Ошибка "не на единицу": одна из распространенных ошибок – забывание учесть отсутствующее число при переборе диапазона. Итерируя до n вместо n+1, мы можем пропустить недостающее число. В фрагменте кода мы правильно итерируем до n.
Эффективность. Подход сравнения имеет временную сложность O(n²), так как мы перебираем массив и для каждого элемента проверяем его наличие с помощью includes
. Для больших массивов этот подход может оказаться не самым эффективным. С другой стороны, математический подход имеет временную сложность O(n) и более эффективен для больших наборов данных.
Краткое содержание:
В этой статье мы рассмотрели проблему поиска пропущенного числа в массиве последовательных целых чисел. Мы предоставили фрагменты кода JavaScript, которые решают проблему, используя как подход сравнения, так и математический подход. Кроме того, мы обсудили распространенные заблуждения, такие как случайные ошибки и эффективность различных подходов. В то время как подход сравнения хорошо работает для небольших массивов, математический подход более эффективен для больших наборов данных. Зная об этих неверных представлениях и выбирая подходящий подход в зависимости от масштаба проблемы, вы можете уверенно решать аналогичные задачи.
Удачного кодирования!
Надеюсь, что приведенная выше статья дала лучшее понимание. Если у вас есть какие-либо вопросы относительно областей, которые я обсуждал в этой статье, области улучшения, не стесняйтесь комментировать ниже.
[Раскрытие информации: эта статья является совместным творением, в котором мои собственные идеи сочетаются с помощью ChatGPT для оптимальной артикуляции.]