I'm trying to solve the problem which is defined as:

we are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively. Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The function should not return the final sorted array, but instead, be stored inside the array nums1. To accommodate this, nums1 has a length of m n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

I have written the following code in python :

def merge(nums1, m, nums2, n):
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1=nums1[:m]
       # print("before",nums1)
        for i in nums1[m:n]:
            i=0
       # print("after1",nums1)
        nums1[m:n]=nums2[:n]
        nums1.sort()
       # print(nums1)
merge([0],0,[1],1)

I have tried to submit the solution but showing up as an error. Can anyone find the solution to the given problem? Please do something with the above code, not anything from outside.

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. 

CodePudding user response：

You would like us to start from your code attempt, but none of the statements in your attempt are salvageable in an efficient solution:

• nums1=nums1[:m]. This statement creates a new list, storing its reference in the variable that had a reference to the original input list. Thereby you lose the reference to the input list, and make it impossible to change anything in that list -- which was the purpose of this function.
• for i in nums1[m:n]: In an efficient solution, you would not create a new list (like with using slice notation).
• i=0: there is no benefit in repeating this in a loop. This is an assignment to a variable, not to a member of a list. It seems you thought this loop would clear part of the original list, but you cannot clear a list by assigning 0 to a variable. Moreover, there is no need to clear anything in any list for this code challenge.
• nums1[m:n]=nums2[:n] although this copies the second list into nums1, this is copying it in a local list -- a list that the caller has no access to. Secondly, you would need to use the free space in the left list to efficiently merge the data. Now by having copied all values from the second list in it, you don't have any space anymore for such merge.
• nums1.sort(). Calling sort defeats the purpose of the code challenge. sort doesn't use the knowledge that we're dealing with 2 sorted lists, and can only offer a time complexity of O(nlogn), while you can do it with a complexity of O(n).

So... nothing in your code can stay. It goes wrong from the first statement onwards, and takes the wrong approach.

The algorithm that should be implemented will have an index going from end to start in the nums1 and store the greatest value there from the values that have not yet been stored that way. As the input lists are sorted, there are only 2 values candidate for this operation.

Here is an implementation:

def merge(nums1, m, nums2, n):
    # Let m and n refer to the last used index in given lists
    m -= 1
    n -= 1
    for i in range(m   n   1, -1, -1):
        if n < 0 or m >= 0 and nums1[m] > nums2[n]:
            nums1[i] = nums1[m]
            m -= 1
        else:
            nums1[i] = nums2[n]
            n -= 1

CodePudding user response：

What you are asking for is just the classic function used within the merge sort algorithm. You can find many solutions online.

Here is a possible solution:

def merge(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    for last in range(m   n - 1, -1, -1):
        if i < 0:
            nums1[last] = nums2[j]
            j -= 1
        elif j < 0:
            nums1[last] = nums1[i]
            i -= 1
        elif nums1[i] < nums2[j]:
            nums1[last] = nums2[j]
            j -= 1
        else:
            nums1[last] = nums1[i]
            i -= 1

Example:

>>> nums1 = [1, 3, 5, 7, 0, 0, 0]
>>> nums2 = [4, 6, 8]
>>> m = 4
>>> n = 3
>>> merge(nums1, m, nums2, n)
>>> nums1
[1, 3, 4, 5, 6, 7, 8]

Another example:

>>> nums1 = [1, 2, 3, 0, 0, 0]
>>> nums2 = [2, 5, 6]
>>> m = 3
>>> n = 3
>>> merge(nums1, m, nums2, n)
>>> nums1
[1, 2, 2, 3, 5, 6]

If you want to keep your original code and fix it then you can do this:

def merge(nums1, m, nums2, n):
    nums1[m:] = nums2
    nums1.sort()

Beware that this is much slower than my solution, and it's not the standard way to solve this well known problem.