88. Merge Sorted Array

leetcode easy

#array#csharp#easy#leetcode#sort

Task

Вам даны два массива целых чисел nums1 и nums2, отсортированных в порядке неубывания, а также два целых числа m и n, представляющих количество элементов в nums1 и nums2 соответственно.

Слейте nums1 и nums2 в один массив, отсортированный в порядке неубывания.

Итоговый отсортированный массив не должен возвращаться функцией, а должен храниться внутри массива nums1. Чтобы это обеспечить, длина nums1 составляет m + n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. Длина nums2 составляет n.

Пример:

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

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

Explanation: The arrays we are merging are [1,2,3] and [2,5,6].

The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

C# solution

matched/original

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums1Copy = new int[m];
        Array.Copy(nums1, 0, nums1Copy, 0, m);
        int p1 = 0;
        int p2 = 0;
        for (int p = 0; p < m + n; p++) {
            if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {
                nums1[p] = nums1Copy[p1++];
            } else {
                nums1[p] = nums2[p2++];
            }
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public void Merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int>& nums1Copy = new int[m];
        Array.Copy(nums1, 0, nums1Copy, 0, m);
        int p1 = 0;
        int p2 = 0;
        for (int p = 0; p < m + n; p++) {
            if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {
                nums1[p] = nums1Copy[p1++];
            } else {
                nums1[p] = nums2[p2++];
            }
        }
    }
}

Java solution

matched/original

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums1Copy = new int[m];
        for (int i = 0; i < m; i++) {
            nums1Copy[i] = nums1[i];
        }
        int p1 = 0;
        int p2 = 0;
        for (int p = 0; p < m + n; p++) {
            if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {
                nums1[p] = nums1Copy[p1++];
            } else {
                nums1[p] = nums2[p2++];
            }
        }
    }
}

JavaScript solution

matched/original

var merge = function (nums1, m, nums2, n) {
    let nums1Copy = nums1.slice(0, m);
    let p1 = 0;
    let p2 = 0;
    for (let p = 0; p < m + n; p++) {
        if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {
            nums1[p] = nums1Copy[p1++];
        } else {
            nums1[p] = nums2[p2++];
        }
    }
};

Python solution

matched/original

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1_copy = nums1[:m]
        p1 = 0
        p2 = 0
        for p in range(n + m):
            if p2 >= n or (p1 < m and nums1_copy[p1] <= nums2[p2]):
                nums1[p] = nums1_copy[p1]
                p1 += 1
            else:
                nums1[p] = nums2[p2]
                p2 += 1

Go solution

matched/original

func merge(nums1 []int, m int, nums2 []int, n int) {
    nums1Copy := append([]int(nil), nums1[:m]...)
    p1 := 0
    p2 := 0
    for p := 0; p < m+n; p++ {
        if p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2]) {
            nums1[p] = nums1Copy[p1]
            p1++
        } else {
            nums1[p] = nums2[p2]
            p2++
        }
    }
}

Explanation

Algorithm

1️⃣

Самая простая реализация заключалась бы в создании копии значений в nums1, называемой nums1Copy, а затем использовании двух указателей для чтения и одного указателя для записи для чтения значений из nums1Copy и nums2 и записи их в nums1.

2️⃣

Инициализируйте nums1Copy новым массивом, содержащим первые m значений nums1.

Инициализируйте указатель для чтения p1 в начале nums1Copy.

Инициализируйте указатель для чтения p2 в начале nums2.

3️⃣

Инициализируйте указатель для записи p в начале nums1.

Пока p все еще находится внутри nums1:

Если nums1Copy[p1] существует и меньше или равно nums2[p2]:

Запишите nums1Copy[p1] в nums1[p], и увеличьте p1 на 1.

Иначе

Запишите nums2[p2] в nums1[p], и увеличьте p2 на 1.

Увеличьте p на 1.

😎