День-18 Merge Sorted Array

Фон

Эта задача является частью введения в структуры данных развлечения с массивами-101 на LeetCode. Под подзаголовком вставляя элементы в массив.

Постановка задачи

Учитывая два сортированных целочисленных массива Nums1 и Nums2, Merge Nums2 в Nums1 в виде одного сортированного массива.

Примечание:

Количество элементов, инициализированных в Nums1 и Nums2, составляет M и N соответственно.
Вы можете предположить, что Nums1 имеет достаточно места (размер, который больше или равен M + N), чтобы удерживать дополнительные элементы от Nums2.

Пример

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

Output: [1,2,2,3,5,6]

Решение подход 1

Случай 1: nums1 [i]

Сравните один элемент из обоих массивов. Если элемент в 1 -м массиве меньше, то элемент во 2 -м массиве. Вставьте элемент в массив 3. Увеличьте счетчик I массива 1 на 1.

Случай 2: nums2 [j]

Если элемент в массиве 2 меньше элемента в массиве 1. Затем вставьте элемент в массив 3. Увеличьте счетчик j массива 2 к следующему элементу.

Случай 3: Nums1 [i] [j]

Вставьте Nums2 [j] в массив 3. Приращение Оба счетчика I и J на 1.

В результате массив 3 будет окончательным сортированным массивом.

Вещи, которые нужно наблюдать

Мы используем дополнительный массив. Массив 3, это означает дополнительное пространство. Как задается в вопросе. Решение должно быть решением на месте.
Обратите внимание, что приведенный ниже код скелета не упоминает тип возврата. Следовательно, хотя NUMS3 является объединенным сортированным массивом. Это не может быть возвращено.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        i = 0
        j = 0 
        nums3 = []
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                nums3.append(nums1[i])
                i += 1
            elif nums1[i] > nums2[j]:
                nums3.append(nums2[j])
                j += 1
            elif nums1[i] == nums2[j]:
                nums3.append(nums1[i])
                i += 1
                nums3.append(nums2[j])
                j += 1

        while i < m:
            nums3.append(nums1[i])
            i += 1

        while j < n:
            nums3.append(nums2[j])
            j += 1

Решение подход 2

Держите логику слияния той же.
Вместо возвращения Nums3. Мы можем выполнять задание элемента. И скопируйте все элементы Nums3 в Nums1.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        i = 0
        j = 0 
        nums3 = []
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                nums3.append(nums1[i])
                i += 1
            elif nums1[i] > nums2[j]:
                nums3.append(nums2[j])
                j += 1
            elif nums1[i] == nums2[j]:
                nums3.append(nums1[i])
                i += 1
                nums3.append(nums2[j])
                j += 1

        while i < m:
            nums3.append(nums1[i])
            i += 1

        while j < n:
            nums3.append(nums2[j])
            j += 1


        for i in range(0, len(nums1)):
            nums1[i] = nums3[i]

Участие

Мы смогли объединить два отсортированных массива.
Сложность времени – O (n)
Временная сложность добавления – O (1)
Как все значения сама Nums1 изменяются. Таким образом, нет необходимости возвращать что -либо. Следовательно, решение принимается.
List.insert может быть не выходом. Причина в том, что это встроенная функция. Во -вторых, вставка в определенном индексе добавляет к сложности времени.

Вещи, которые нужно выяснить

Решение должно быть решением на месте. Это не необходимо использовать дополнительную память. Как решить его без использования дополнительного места?
Приведет ли оптимизация сложности пространства к увеличению временной сложности?

Оригинал: “https://dev.to/mridubhatnagar/day-18-merge-sorted-array-khm”

Фон