Решение на JavaScript для Array.diff, проблемы кодовых войн 6 кю
Реализуйте функцию различия, которая вычитает один список из другого и возвращает результат.
Он должен удалить все значения из списка
a
, которые присутствуют в спискеb
, сохраняя их порядок.
arrayDiff([1,2],[1]) == [2]
Если значение присутствует в
b
, все его вхождения должны быть удалены из другого
arrayDiff([1,2,2,2,3],[2]) == [1,3]
Прежде чем читать решение, приведенное ниже, попробуйте решить Array.diff, задачу 6 кю, самостоятельно в Codewars.
Понять проблему
Хотя название проблемы и подсказка предполагают, что элементы массива аргумента 2 должны быть удалены из массива аргумента 1, альтернативный, но эквивалентный способ думать о проблеме - с точки зрения включения. Возвращаемый массив должен включать элементы массива аргумента 1 и не включать элементы массива аргумента 2.
Вторая часть подсказки указывает, что все вхождения элементов в массиве аргументов 1 не должны возвращаться, если это элемент в массиве аргументов 2. Проще представить подсказку в терминах включения, а не в терминах различия, вычитания или удаления.
С точки зрения включения, приглашение выглядит следующим образом: вернуть массив, который включает элементы массива аргументов 1 и не включает никаких элементов массива аргументов 2.
Входы и крайние случаи
В самой подсказке есть два ввода. Решение должно как минимум обрабатывать эти:
- arrayDiff ([1, 2], [1]) == [2]
- arrayDiff ([1, 2, 2, 2, 3], [2]) == [1, 3]
Некоторые крайние случаи, которые следует учитывать, - это пустые массивы. Массив аргумента 1, массив аргумента 2 или оба могут быть пустыми:
- arrayDiff ([], [1, 2]) == []
- arrayDiff ([1, 2], []) == [1, 2]
- arrayDiff ([], []) == []
Псевдокодирование решения
В целом, я хочу начать с пустого массива, добавить элементы, отвечающие определенным условиям, и вернуть этот массив. Для каждого элемента в массиве аргументов 1 я хочу проверить, включен ли он в массив аргументов 2. Если он не включен, я хочу вставить этот элемент в свой возвращаемый массив. Это должно обрабатывать вводимые выше данные.
Перед просмотром массива аргумента 1 следует обработать крайние случаи. Граничный случай 1 и 3 возвращают пустой массив, если массив аргумента 1 пуст, а граничный случай 2 возвращает массив аргумента 1, если массив аргумента 2 пуст. Обработка этого до любых циклов позволяет сэкономить на вычислениях, поскольку они могут быть возвращены без каких-либо циклов.
Помещаем эту общую стратегию в псевдокод:
- Создайте функцию с именем «arrayDiff», которая принимает в качестве аргументов два массива: «array1» и «array2».
- Обработка крайних случаев:
a. Если длина «array1» равна 0, вернуть пустой массив
b. Если длина «array2» равна 0, вернуть «array1». - Создайте возвращаемый массив с именем «returnArray».
- Прокрутите "array1"
- Если элемент не включен в «array2», переместите элемент в «returnArray».
- Вернуть returnArray
Напишите решение
// Создаем функцию с именем «arrayDiff», которая принимает в качестве аргументов два массива, «array1» и «array2».
function arrayDiff (array1, array2) {
// Обработка крайних случаев: (a) Если длина «array1» равна 0, вернуть пустой массив
if (array1.length === 0) {return []}
// Обрабатывать крайние случаи: (b) Если длина «array2» ”Равно 0, верните“ array1 ”
if (array2.length === 0) {return array1}
// Создайте возвращаемый массив с именем“ returnArray ”< br /> let returnArray = [];
// Цикл через «array1»
array1.forEach (function included (element) {
// Если элемент не включен в «array2» , вставьте его в «returnArray»
if (! array2.includes (element)) {returnArray.push (element)}
})
// Возвращаем returnArray
return returnArray;
}
Проверить решение
Консоль, регистрирующая входные данные и крайние случаи, вернула ожидаемые массивы. Решение работает как положено.
Оцените решение
С точки зрения удобочитаемости, инженеры могут легко оценить это решение и поддержать его в будущем.
Что касается временной сложности, есть возможности для улучшения. Метод forEach, который представляет собой простой цикл, имеет временную сложность O (n). Метод include также является простым циклом, поэтому его временная сложность также O (n). Поскольку метод include вложен внутрь метода forEach, временная сложность решения составляет O (n * n) = O (n²). Следовательно, с точки зрения временной сложности есть возможности для улучшения. Это было бы медленным решением, если длина вводимых массивов велика.
Некоторые другие крайние случаи, которые следует учитывать, - это если входные данные не являются массивами. Это можно учесть, включив дополнительное условие перед методом forEach. Если какой-либо из аргументов не является массивами, он может вернуть сообщение о том, что функция ожидает массивы в качестве входных данных.
Ваше решение
Как вы подошли к этой проблеме? Вы использовали разные методы JavaScript? Удалось ли вам реализовать решение с меньшей временной сложностью? Вы вообще использовали другой язык программирования?
Я буду рад получить известие от вас! Пожалуйста, поделитесь, как вы решили эту проблему, в комментариях ниже, чтобы другие и я могли узнать об этом.