Знаходження відсутнього елемента в масиві JS (Missing Element)
Вступ
Задача "Знаходження відсутнього елемента" є однією з найпопулярніших задач на технічних співбесідах і лайвкодингу. Вона перевіряє ваше розуміння алгоритмів, математики та здатність оптимізувати рішення.
Постановка задачі
Дано: Масив цілих чисел від 1 до n+1, де один елемент відсутній.
Знайти: Відсутній елемент.
Приклад:
// Вхідний масив: [1, 2, 4, 5, 6]
// Відсутній елемент: 3
// Повний масив має бути: [1, 2, 3, 4, 5, 6]
Підходи до розв'язання
1. Математичний підхід (Сума арифметичної прогресії)
Ідея: Використовуємо формулу суми арифметичної прогресії для знаходження очікуваної суми, а потім віднімаємо фактичну суму.
function findMissingElement(arr) {
const n = arr.length + 1; // Довжина повного масиву
const expectedSum = (n * (n + 1)) / 2;
const actualSum = arr.reduce((sum, num) => sum + num, 0);
return expectedSum - actualSum;
}
// Приклад використання
const numbers = [1, 2, 4, 5, 6];
console.log(findMissingElement(numbers)); // 3
Переваги:
- Часова складність: O(n)
- Просторова складність: O(1)
- Елегантне рішення
Недоліки:
- Може виникнути переповнення для великих чисел
- Працює лише для послідовних чисел
2. Використання Set для швидкого пошуку
Ідея: Створюємо Set з наявних елементів і перевіряємо кожне число від 1 до n+1.
function findMissingElementWithSet(arr) {
const numSet = new Set(arr);
const n = arr.length + 1;
for (let i = 1; i <= n; i++) {
if (!numSet.has(i)) {
return i;
}
}
return -1; // Якщо не знайдено (не повинно статися)
}
// Приклад використання
const numbers = [1, 2, 4, 5, 6];
console.log(findMissingElementWithSet(numbers)); // 3
Переваги:
- Інтуїтивно зрозумілий підхід
- Швидкий пошук O(1) в Set
Недоліки:
- Просторова складність: O(n)
- Менш ефективний за пам'яттю
3. Підхід з сортуванням
Ідея: Сортуємо масив і перевіряємо послідовність.
function findMissingElementWithSort(arr) {
arr.sort((a, b) => a - b);
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== i + 1) {
return i + 1;
}
}
return arr.length + 1; // Останній елемент відсутній
}
// Приклад використання
const numbers = [5, 1, 4, 2, 6];
console.log(findMissingElementWithSort(numbers)); // 3
Переваги:
- Не потребує знання максимального значення
- Працює з несортованими масивами
Недоліки:
- Часова складність: O(n log n) через сортування
- Модифікує вхідний масив
4. XOR підхід (Найбільш оптимальний)
Ідея: Використовуємо властивість XOR: a ⊕ a = 0 і a ⊕ 0 = a.
function findMissingElementXOR(arr) {
const n = arr.length + 1;
let xorAll = 0;
let xorArr = 0;
// XOR всіх чисел від 1 до n
for (let i = 1; i <= n; i++) {
xorAll ^= i;
}
// XOR всіх елементів масиву
for (let num of arr) {
xorArr ^= num;
}
return xorAll ^ xorArr;
}
// Приклад використання
const numbers = [1, 2, 4, 5, 6];
console.log(findMissingElementXOR(numbers)); // 3
Переваги:
- Часова складність: O(n)
- Просторова складність: O(1)
- Не має проблем з переповненням
Аналіз складності
| Підхід | Часова складність | Просторова складність | Примітки |
|---|---|---|---|
| Математичний | O(n) | O(1) | Найкращий для малих чисел |
| Set | O(n) | O(n) | Легко зрозуміти |
| Сортування | O(n log n) | O(1) | Найповільніший |
| XOR | O(n) | O(1) | Найнадійніший |
Поради для лайвкодингу
1. Уточнення вимог
// Завжди запитуйте:
// - Чи можуть бути дублікати?
// - Чи завжди починається з 1?
// - Чи відсутній тільки один елемент?
// - Яка максимальна довжина масиву?
2. Почніть з простого рішення
// Спочатку покажіть найпростіше рішення
function findMissingSimple(arr) {
// Створюємо повний масив і порівнюємо
const n = arr.length + 1;
const fullArray = Array.from({length: n}, (_, i) => i + 1);
for (let num of fullArray) {
if (!arr.includes(num)) {
return num;
}
}
}
3. Поступово оптимізуйте
// Потім покажіть оптимізацію
function findMissingOptimized(arr) {
const n = arr.length + 1;
const expectedSum = (n * (n + 1)) / 2;
const actualSum = arr.reduce((sum, num) => sum + num, 0);
return expectedSum - actualSum;
}
4. Обговоріть edge cases
function findMissingRobust(arr) {
// Перевірка на порожній масив
if (arr.length === 0) {
return 1;
}
// Перевірка на один елемент
if (arr.length === 1) {
return arr[0] === 1 ? 2 : 1;
}
// Основна логіка
const n = arr.length + 1;
const expectedSum = (n * (n + 1)) / 2;
const actualSum = arr.reduce((sum, num) => sum + num, 0);
return expectedSum - actualSum;
}
Практичні приклади
Приклад 1: Базовий випадок
const test1 = [1, 2, 4, 5];
console.log(findMissingElement(test1)); // 3
Приклад 2: Відсутній перший елемент
const test2 = [2, 3, 4, 5];
console.log(findMissingElement(test2)); // 1
Приклад 3: Відсутній останній елемент
const test3 = [1, 2, 3, 4];
console.log(findMissingElement(test3)); // 5
Приклад 4: Великий масив
const test4 = Array.from({length: 999}, (_, i) => i + 1);
test4.splice(500, 1); // Видаляємо 501-й елемент
console.log(findMissingElement(test4)); // 501
Варіації задачі
1. Кілька відсутніх елементів
function findMissingElements(arr, n) {
const present = new Set(arr);
const missing = [];
for (let i = 1; i <= n; i++) {
if (!present.has(i)) {
missing.push(i);
}
}
return missing;
}
2. Масив не починається з 1
function findMissingInRange(arr, start, end) {
const expectedSum = ((end - start + 1) * (start + end)) / 2;
const actualSum = arr.reduce((sum, num) => sum + num, 0);
return expectedSum - actualSum;
}
Стратегія для співбесіди
- Слухайте уважно - переконайтеся, що розумієте задачу
- Задавайте питання - уточніть обмеження та edge cases
- Почніть з простого - покажіть базове рішення
- Поясніть складність - обговоріть Big O
- Оптимізуйте - покажіть кращі варіанти
- Тестуйте - перевірте на різних випадках
Висновки
Задача "Знаходження відсутнього елемента" має кілька елегантних рішень. Математичний підхід найкращий для більшості випадків, але XOR підхід найнадійніший для великих чисел. Під час лайвкодингу важливо почати з простого рішення і поступово його оптимізувати, обговорюючи переваги та недоліки кожного підходу.
Рекомендований підхід для співбесіди:
- Почніть з математичного підходу
- Обговоріть можливі проблеми з переповненням
- Покажіть XOR підхід як альтернативу
- Протестуйте на edge cases
Пам'ятайте: важливо не лише знайти правильне рішення, а й продемонструвати своє мислення та здатність оптимізувати код.