Merge sorted arrays

Let’s solve the problem of merging two sorted arrays. This can be found here Merge Sorted Array

Define the problem

There are two arrays nums1 and nums2, sorted in non-decreasing order, and two numbers m and n, which indicate the number of elements in the respective arrays.
It is necessary to combine the two arrays into one array sorted in non-decreasing order.
The result must be returned in an array nums1.

An example of input data

Example 1

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

Example 2.

Input data:
nums1 = [1]
m = 1
nums2 = []
n = 0
Result:
[1]

Example 3.

Input data:
nums1 = [0]
m = 0
nums2 = [1]
n = 1
Result:
[1]

Solution .

We need to iterate through each of the arrays from beginning to end. At each iteration, we take the minimum element and put it into a new array. Then we need to copy this array into nums1.
However, in this case we will use additional memory. This can be optimized. By convention, m + n space is allocated in nums1 array. So, if we start filling the arrays from the end, we can do without allocating extra memory.

The solution in steps

1) First we need to initialize the counters.

var index1: Int = m - 1
var index2: Int = n - 1
var index: Int = m + n - 1
Enter fullscreen mode Exit fullscreen mode

For the first and second array we will use the variables index1 and index2, respectively. The variable index will be used to track the resulting index.

2) Then we define the loop conditions.

while (index >= 0 && index2 >= 0) {
   ...
}
Enter fullscreen mode. Exit fullscreen mode.

There are two conditions to be checked. If the result array index is equal to zero, then we have already filled up the entire array, and we need to stop iterating. If the index of the second array is equal to zero, it means that we have completely iterated over the second array. The rest of the first array is in the right order, and we can safely end our loop.

3) Next, we need to implement the conditions for selecting an element and updating the index

if (index1 >= 0 && nums1[index1] > nums2[index2]) {
    nums1[index] = nums1[index1]
    index1--
} else {
    nums1[index] = nums2[index2]
    index2--
}
index--
Enter fullscreen mode Exit fullscreen mode

We check that we have not reached the beginning of the first list, and that the next element in the first list is larger than the next element in the second list. Then take an item from the first list and decrease counter of the first list. Otherwise, take an item from the second list and decrease the counter of the second list. The total counter is reduced at each iteration.

Estimation of complexity

  • By time — O(nums1.length + nums2.length). We completely traverse each of the arrays.
  • By memory — O(1). The amount of memory used does not depend on the size of the input arrays, because only indexes are used to solve the problem.

Complete solution

fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int) {
    var index1: Int = m - 1
    var index2: Int = n - 1
    var index: Int = m + n - 1
    while (index >= 0 && index2 >= 0) {
        if (index1 >= 0 && nums1[index1] > nums2[index2]) {
            nums1[index] = nums1[index1]
            index1--
        } else {
            nums1[index] = nums2[index2]
            index2--
        }
        index--
    }
}
Enter fullscreen mode Exit fullscreen mode

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