LeetCode. Merge Sorted Array [Sorting and Searching]

Problem:

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input: nums1 = [1,2,3,0,0,0], m = 3

nums2 = [2,5,6], n = 3

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

 

-Summary-

1. first we remove extra zeros in the nums1 list

2. Add nums2 list to nums1

3. Sort by using .sort() function

 

 

파이썬의 built in function인 .sort()함수를 썼지만, 쓰지 않고는 아래와 같은 방식으로 풀수 있다.

leetcode.com/problems/merge-sorted-array/discuss/29699/Clean-python-code

class Solution(object):
    def merge(self, nums1, m, nums2, n):
    	#loop until number of nums1 or nums2 is not 0
        while m > 0 and n > 0:
        #Compare from the end of the each list
        	#if nums1's number greater than nums2's number.
            if nums1[m - 1] > nums2[n - 1]:
            	#copy the number to the last empty slot of the list
                nums1[m + n - 1] = nums1[m - 1]
                #decrease m index
                m -= 1
            #if num1's number is smaller or equal to the num2's number.    
            else:
            	#copy the number to the last empty slot of the list
                nums1[m + n - 1] = nums2[n - 1]
                #decease n index
                n -= 1
        #Special case. if m is finished earlier. All nums2 number should be less than nums1 number.
        nums1[:n] = nums2[:n]

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]