Давайте найдем недостающие числа в массивах, используя сравнение или математические подходы. Избегайте распространенных заблуждений

В мире программирования решение головоломок и задач является важной частью оттачивания наших навыков решения проблем. Одна из таких интригующих головоломок — найти пропущенное число в массиве последовательных целых чисел. Эта проблема может показаться простой на первый взгляд, но она может быстро стать сложной, если вы не знаете о некоторых распространенных заблуждениях. В этой статье мы рассмотрим постановку задачи, предоставим фрагменты кода 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;
}
  1. Функция findMissingNumberComparison принимает на вход массив arr.
  2. Мы инициализируем переменную missingNumber значением 0.
  3. Используя цикл for, мы итерируем от 1 до n (включительно), поскольку отсутствующее число может находиться в диапазоне от 1 до n+1.
  4. Внутри цикла мы проверяем наличие текущего числа в массиве с помощью метода includes.
  5. Если число не найдено в массиве, это означает, что это отсутствующее число. Мы присваиваем его переменной missingNumber и выходим из цикла.
  6. Наконец, мы возвращаем недостающее число в качестве вывода функции.

Математический подход:

Теперь давайте рассмотрим более эффективный математический подход к решению проблемы пропущенного числа:

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;
}
  1. Функция findMissingNumberMath принимает на вход массив arr.
  2. Мы вычисляем ожидаемую сумму последовательных чисел в диапазоне (от 1 до n+1) по формуле (n * (n + 1)) / 2, где n — длина входного массива плюс один.
  3. Затем мы вычисляем фактическую сумму элементов в массиве, используя функцию reduce, которая выполняет итерацию по каждому элементу и накапливает их сумму.
  4. Недостающее число можно найти, вычитая фактическую сумму из ожидаемой суммы.
  5. Наконец, мы возвращаем недостающее число в качестве вывода функции.

Пример набора данных и выполнения:

Давайте рассмотрим массив [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 для оптимальной артикуляции.]