88. Объединить отсортированный массив [leetcode] [c++]

Менять местами nums1 и nums2 не имеет смысла, поскольку результат должен полностью храниться внутри nums1.

Кроме того, последнее условие не требуется; если следующий элемент, добавляемый к выводу, не из первого вектора, то он обязательно должен быть из второго. Осталось проверить границы: если в первом векторе не осталось элементов, мы можем брать элементы только из второго и наоборот.

for (; iResult >= 0 && iNums2 >= 0; iResult--) {      
    if (iNums1 < 0 || iNums2 >= 0 && nums2[iNums2] > nums1[iNums1]){
        nums1[iResult] = nums2[iNums2--];
    } else {
        nums1[iResult] = nums1[iNums1--];
    }
}

Аннотированное решение

Исходный код ниже взят из ОП. Я добавил множество комментариев, объясняющих, что пошло не так.

Я использую операторы препроцессора #if-else-endif, чтобы изолировать плохой код и вставить свои исправления. Это означает, что вы можете скопировать и вставить это обратно в исходную программу, и все должно работать. Конечно, после того, как вы его очистите, он станет намного красивее.

void Solution::merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n)
{
    int iNums1 = m - 1;
    int iNums2 = n - 1;
    int iResult = m + n - 1;

#if 0
    // This loop will stop early when `iNums1 >= 0 && iNums2 < 0`.
    for (; iResult >= 0 && iNums2 >= 0; iResult--)
    {
#else
    // If `iResult` is not negative, then you KNOW that either 
    // `iNums1` or `iNums2` (or both) are also non-negative.
    // So, keep looping!
    for (; iResult >= 0; iResult--)
    {
#endif
        if (iNums2 < 0)
        {
            // This is perfect. Note, however, when you had the wrong 
            // termination condition on the for-statement, this was, 
            // effectively, a "no-op." That's because `iNums2` could 
            // never be negative.
            break;;
        }
#if 0
        // There is nothing wrong with this test: the program will work 
        // fine if you leave it as it is. The second test, however, is 
        // redundant. We already know that `iNums2` in not negative.
        // We just tested it!
        else if (iNums1 < 0 && iNums2 >= 0)
#else
        else if (iNums1 < 0)
#endif
        {
#if 0
            // Swapping vectors is the wrong idea.
            // You will lose the data already present in `nums1`.
            std::swap(nums2, nums1);
            break;
#else
            // When `iNums1` goes negative, you can simply copy 
            // whatever remains in `nums2`.
            while (iResult >= 0) {
                nums1[iResult--] = nums2[iNums2--];
            }
            break;
#endif
        }
        else if (nums2[iNums2] > nums1[iNums1])
        {
            nums1[iResult] = nums2[iNums2--];
        }
#if 0
        // You are working too hard here. 
        else if (iResult <= m 
            && nums1[iResult - 1] <= nums2[iNums2] 
            && nums1[iResult] > nums2[iNums2])
        {
            nums1[iResult + 1] = nums1[iResult];
            nums1[iResult] = nums2[iNums2--];
        }
#else
        else
        {
            // Since we know that `nums2[iNums2] > nums1[iNums1]` 
            // is false (because we just tested it), then 
            // `nums1[iNums1]` must be the one that goes in the 
            // result.
            nums1[iResult] = nums1[iNums1--];
        }
#endif
    }
}

Фреймворк для решения проблем LeetCode

Я использую одну и ту же «инфраструктуру» для всех задач LeetCode.

Все начинается с функции main, простого драйвера, который позволяет мне добавлять столько примеров, сколько я захочу. Я начал с трех примеров с сайта LeetCode. Затем я добавил неудавшийся тест из ОП и неизбежный (и, смею сказать, патологический) граничный тест, где оба вектора пусты.

int main()
{
    std::cout << "LeetCode 88. Merge Sorted Array"
        "\nhttps://leetcode.com/problems/permutations-ii/"
        "\n\n";
    solve("Example 1", { 1,2,3,0,0,0 }, 3, { 2,5,6 }, 3);
    solve("Example 2", { 1 }, 1, {}, 0);
    solve("Example 3", { 0 }, 0, { 1 }, 1);
    solve("Example 4", { 2,0 }, 1, { 1 }, 1);
    solve("Example 5", {}, 0, {}, 0);
}

Функция solve организует решение и отображает результаты так же, как примеры показаны на веб-сайте LeetCode.

Я использую параметры по значению для передаваемых векторов. Таким образом, аргументы, используемые в функции main, могут быть заключены в списки инициализаторов.

void solve(
    std::string_view heading,
    std::vector<int> nums1,
    int const m,
    std::vector<int> nums2,
    int const n)
{
    std::cout
        << heading
        << "\n"
        << "\n  Input: nums1 = " << put_vector(nums1)
        << ", m = " << m
        << ", nums2 = " << put_vector(nums2)
        << ", n = " << n;
    Solution{}.merge(nums1, m, nums2, n);
    std::cout
        << "\n  Output: " << put_vector(nums1)
        << "\n\n";
}

Небольшой набор инструментов используется снова и снова. На этот раз это был шаблон класса put_vector, реализованный в стиле манипулятора ввода-вывода.

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

template< typename T >
class put_vector
{
    std::vector<T> const& v;
public:
    put_vector(std::vector<T> const& v) : v{ v } {}
private:
    void put(std::ostream& ost) const {
        ost.put('[');
        if (!v.empty()) {
            ost << v.front();
            for (std::size_t i{ 1u }; i < v.size(); ++i) {
                ost << ',' << v[i];
            }
        }
        ost.put(']');
    }
    friend std::ostream& operator<< (std::ostream& ost, put_vector const& pv) {
        pv.put(ost);
        return ost;
    }
};

Теперь все, что мне нужно сделать, это подключить решение. Я всегда начинаю с заглушки.

// This using declaration allows the LeetCode Solution 
// to be used without modifying its function signature.
// 
// (Shame on you, LeetCode, for teaching programmers to 
// rely on `using namespace std;`.)
using std::vector;

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    }
};

Поскольку я могу скопировать все шаблоны из предыдущих решений LeetCode, эти предварительные действия занимают всего около 5-10 минут. Тогда я смогу запустить программу.

LeetCode 88. Merge Sorted Array
https://leetcode.com/problems/permutations-ii/

Example 1

  Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
  Output: [1,2,3,0,0,0]

Example 2

  Input: nums1 = [1], m = 1, nums2 = [], n = 0
  Output: [1]

Example 3

  Input: nums1 = [0], m = 0, nums2 = [1], n = 1
  Output: [0]

Example 4

  Input: nums1 = [2,0], m = 1, nums2 = [1], n = 1
  Output: [2,0]

Example 5

  Input: nums1 = [], m = 0, nums2 = [], n = 0
  Output: []

Теперь начинается самое интересное...