Дневник Leetcode: Слияние отсортированного массива

https://leetcode.com/problems/merge-sorted-array

задача: даны два отсортированных массива, как получить отсортированный массив. В одном массиве m чисел, а в другом — n. Первый массив имеет длину m+n, поэтому вам не нужно беспокоиться об изменении длины массива.

Эта задача проста, если просто поместить результат в другой массив и в конце мутировать массив m+n. Поэтому мы выберем самый сложный путь O(m+n) с мутацией только на месте.

Первое, что вы должны принять, это то, что значения m и n имеют значение. Это немного обманчиво, потому что легкий маршрут на самом деле не требует этого, поэтому люди могут не заметить этого и пойти по ужасному маршруту.

Второе — вы должны использовать счетчик как есть, не пытайтесь сделать m— для какого-то хитрого трюка, просто используйте обычный индексный цикл, и все будет в порядке.

Однако вы должны учитывать тот факт, что вы не можете просто использовать циклы for. Это происходит потому, что у вас есть два массива и цель — O(m+n), обычные циклы for не могут этого сделать.

Поэтому это цикл while с условиями.

Что такое условия? Легко начать с чего-то вроде:

но это не сработает, потому что конечная длина равна m+n, так что, вероятно, она больше.

Тогда я подумал следующее:
Q: когда закончится цикл?
A: он заканчивается, когда все числа мутируют на месте.
Q: сколько всего чисел?
О: m+n
Q: но как мне представить это в коде?
A: считать до m+n?
Q: это кажется неправильным …

Если у вас возникло такое чувство, значит, вам чего-то не хватает для того, чтобы прийти к правильному ответу. Вы должны сделать шаг назад и посмотреть на другие части проблемы.

Я вернулся к части вопроса, касающейся мутации на месте. Мутация массива на месте должна немедленно привести вас к необходимости иметь третий массив для хранения значений; это продолжение наличия третьей переменной для замены двух значений в массиве.
Допустим, это: const holdM = [];.

С учетом этого должно быть очевидно, что цикл завершится, когда:

Теперь мы наконец-то можем перейти к написанию основного кода!

Учитывая задачу, у нас есть две части кода:
1.) найти текущее минимальное значение
2.) мутировать массив с текущим min

Первая часть проста, у нас есть 3 значения:
1.) текущее значение массива[m]
2.) значение массива array2[n]
3.) значение holderM

Однако мы должны позаботиться о каждом случае, потому что
1.) array[m] может быть неопределенным, так как длина массива = m+n и имеет значение только в первом m.
2.) массив2 имеет только n значений, в коде необходимо представить «массив2 исчерпан».
3.) держательМ может иметь или не иметь значений, также в массиве может быть более одного значения.

Чтобы позаботиться об этом, мы можем перевести код в:

почему только holdM[0]? потому что наименьшее значение находится в начале массива (вы также можете выбрать последнее, не имеет значения).

Итак, мы наконец-то получили:

теперь нам нужно что-то сделать с минимальным значением.
Нам нужно рассмотреть 3 случая:
1.) minVal = текущее val из M
2.) minVal = текущее значение N
3.) minVal = текущее значение holdM

если
1.) нам не нужно ничего делать, текущее значение уже находится в массиве на своем месте!
2.) это означает, что значения N должны быть на месте M, поэтому вам нужно будет переместить значение M в holdM.
Затем мутировать массив, чтобы поместить значение N.
3.) нужно вытолкнуть значение M в holdM, как это сделано в пункте 2, и мутировать значение holdM.

Последнее, на что следует обратить внимание в этом большом объяснении, это то, что у вас должны быть indexM и indexN. Вы будете увеличивать индексN только тогда, когда N будет наименьшим значением (случай 2), и вы всегда будете увеличивать индексM, потому что вы всегда мутируете на M.

полный код ниже:

var merge = function(nums1, m, nums2, n) {
    const oriM = m;
    const oriN = n;
    let indexM=0, indexN=0, valM, valN, valHold, minVal;
    const holdM = [];
    while(indexN < n || holdM.length) {
        valHold = holdM.length ? holdM[0] : Number.MAX_SAFE_INTEGER;
        valM = indexM < m ? nums1[indexM] : Number.MAX_SAFE_INTEGER;
        valN = indexN < n ? nums2[indexN] : Number.MAX_SAFE_INTEGER;
        minVal = Math.min(valHold, valM, valN);

        if(minVal === valM) {
            indexM++; 
            continue; 
        }
        if (minVal === valN) {
            if (indexM < m) holdM.push(valM);
            nums1[indexM] = valN;
            indexN++;
        } 
        else if(minVal === valHold) {
            if (indexM < m) { holdM.push(valM); }
            nums1[indexM] = holdM.shift();
        }


        indexM++; 
    }
};
Вход в полноэкранный режим Выход из полноэкранного режима

И последнее, интервьюер может быть придирчивым и спросить, в чем большое O этого алгоритма. Это не TRULY O(m + n) из-за shift(). Shift() мутирует весь holdM сразу. Все будет хорошо, если вы признаете эту оговорку и скажете, что это можно легко исправить, если у нас есть третья переменная indexHoldM и использовать ее вместо этого… Затем, не дай бог, они заговорят о длине массива. Тогда вам придется объяснить, что вы можете просто инициировать массив длиной m+n. Надеюсь, что нет… и надеюсь, что этот интервьюер не будет в вашей команде lol …

Пожалуйста, напишите мне в комментариях, если вы хотите увидеть больше материалов, я буду обновлять их нерегулярно, но довольно часто.

Если вы хотите побеседовать со мной 1-1 по поводу вашего резюме или вашей карьерной траектории в целом, пожалуйста, свяжитесь со мной по адресу https://www.fiverr.com/kevtseng.

Социальные сети:
www.twitter.com/KevinTseng1991
https://www.linkedin.com/in/kevintseng1991/

Оцените статью
devanswers.ru
Добавить комментарий