Оптимизированное решение
Намерение
Я нахожусь на пути оттачивания своего набора навыков решения алгоритмических задач. Попутно я хочу поделиться с вами тем, как начать с нуля и постепенно становиться лучше. Эта статья покажет вам, как я научился решать эту распространенную проблему алгоритма, обычно называемую проверкой подпоследовательности в массиве.
Проблема
Сложность: Легко
Имея два входа, первый массив целых чисел, второй меньший массив целых чисел, напишите функцию, которая определяет, является ли второй массив подпоследовательностью первого массива. Например.
const arrOfNums = [1, 3, 5, 9, 12, 18]
const validSequence = [3, 12, 18]
const notValidSequence = [3, 12, 15, 18]
function isValidSubSequence(array, sequence){
//write algo here
//output should be either true or false
}
isValidSubSequence(arrOfNums, validSequence) => true
isValidSubSequence(arrOfNums, notValidSequence) => false
Что такое допустимая подпоследовательность?
Подпоследовательность – это набор вставок, которые появляются в исходном массиве в том же порядке. Имейте в виду, что одиночные целые числа являются допустимыми подпоследовательностями, и целые числа в массиве последовательностей не обязательно должны располагаться рядом. Кроме того, для этой проблемы массив последовательности обычно меньше исходного массива, поскольку обход по массиву последовательности, который больше исходного массива, создаст проблемные пограничные случаи, которые обсуждаются в разделе решения этой статьи. Ниже приведен пример последовательности.
[2, 4, 0, 5, -1, 10] => original array [2, 4, 0, 5, -1, 10] => is a subsequence [2, -1, 10] => is a subsequence [4, 5, 10] => is a subsequence => numbers do not have to be adjacent [2] => is a subsequence [-1] => is a subsequence [2, 4, 0, 5, -1, 10, 11] => is not a subsequence [2, 4, 0, 100000, -1, 10] => is not a subsequence [0, 2, 4, 0, 5, -1, 10] => is not a subsequence
Подход
Моей первоначальной мыслью было пройтись по обоим массивам и сравнить элемент из массива последовательности с каждым элементом исходного массива. Если есть совпадение, я буду продолжать обход, пока не будет пройден весь массив последовательности. Если пройдена вся последовательность, то я знаю, что у меня есть подпоследовательность. Однако я быстро обнаружил проблему: что, если второй элемент в массиве последовательности находится в исходном массиве, но появляется перед первым числом в массиве последовательности.
const array = [1, 3, 5, 6] const sequence = [3, 1, 5, 6] // All numbers are present but do not match the order therefore // sequence is not a subsequence of array
Чтобы решить эту проблему, я использовал метод под названием указатели, который обычно используется при решении алгоритмических задач. Идея состоит в том, чтобы инициализировать указатель, который представляет позицию в массиве, и, если вы хотите изменить положение этого указателя, чтобы он указывал на другой элемент в массиве, вы увеличиваете значение указателя, когда вы пересекаете другой массив. . Например.
const array = [1, 2, 3, 4, 5, 6]
let pointer = 0 #set position of pointer
#return 5
while (pointer < array.length) {
if (array[pointer] === 5) {
return array[pointer]
}
pointer ++
//increase pointer value to move pointer position to the next //element while traversing the array
}
Поэтому мой следующий подход заключается в использовании указателя для сравнения элементов исходного массива и потенциального массива последовательностей. Если элементы между последовательностью и исходным массивом совпадают, я бы переместил позицию в массиве последовательности, чтобы сравнить следующий элемент в массиве последовательности со следующим элементом в исходном массиве и продолжать до тех пор, пока весь массив последовательности не будет сравнен с оригиналом множество. Если пройден весь массив последовательности, то я знаю, что это истинная подпоследовательность исходного массива, если нет, то это не так.
Решение
Поскольку у нас есть входные данные массива, и нам нужно будет пройти по массиву, мы можем использовать цикл for или while для обхода. Кроме того, мы будем использовать указатель для отслеживания нашей позиции в массиве последовательностей.
const arrOfNums = [1, 3, 5, 9, 12, 18]
const validSequence = [3, 12, 18]
const notValidSequence = [3, 12, 15, 18]
function isValidSubSequence(array, sequence) {
let sequenceIdx = 0 // initialize pointer/position
for (let i = 0; i < array.length; i++) {
if (sequenceIdx === sequence.length) {
return true
}
if (sequence[sequenceIdx] === array[i]) {
sequenceIdx++ // if elements match move position
}
}
// returns true if entire sequence array is traversed
return sequenceIdx === sequence.length
}
isValidSubSequence(arrOfNums, validSequence) => true
isValidSubSequence(arrOfNums, notValidSequence) => false
Зачем использовать указатель на массив последовательности, а не на исходный массив?
Что, если мы решим пройтись по массиву последовательности вместо исходного массива? Мы могли бы, но мы не смогли бы получить доступ ко всем элементам исходного массива, кроме одного конкретного случая. Возвращаясь к нашему определению подпоследовательности, в общем случае подпоследовательность должна быть либо точно такой же длины, либо меньше исходного массива. Следовательно, если мы обходим последовательность и если она совпадает с исходным массивом по размеру, то только в этом случае функция может вернуть true, если присутствует подпоследовательность. Однако обычно исходный массив больше массива последовательности. Итак, чтобы удовлетворить требования подпоследовательности, мы должны пройти по исходному массиву, а не по массиву последовательности.
Пространственно-временная сложность
Поскольку длина операции обхода зависит от длины массива, наша временная сложность является линейной или в большой нотации O O (n). Сложность нашего пространства зависит от размера наших инициализированных структур данных. Поскольку мы только инициализируем указатель и никогда не увеличиваем его размер или, другими словами, увеличиваем его размер при выделении памяти, мы можем сказать, что пространственная сложность постоянна или O (1). Имейте в виду, что когда мы увеличиваем значение нашего указателя, он не использует больше памяти для хранения этого нового числа, а скорее обращается к уже инициализированной переменной указателя и присваивает ей новое значение, таким образом сохраняя постоянное пространство.
Вывод
Важно создать прочную основу для того, что такое подпоследовательность, так как подпоследовательности — это обычная тема в продвинутых алгоритмах перемещения, которые представляются в технических интервью. Я расскажу об этих более продвинутых алгоритмах в будущем.
Наконец, я хочу подчеркнуть, что решение проблем с помощью этих алгоритмов может быть трудным, и совершенно естественно чувствовать себя так, как будто вы наткнулись на стену. Если вы нашли эту статью полезной или информативной, пожалуйста, поделитесь своими мыслями ниже.
