Leetcode - Merge Sorted Array

Ji Kim·2020년 10월 7일
0

Algorithm

목록 보기
24/34

Leetcode : Merge Sorted Array

Description

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

Example

Input

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

Output

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

Approach

Use two pointers and compare the last elements of each arrays (as the arrays are sorted, last element is the largest of all). And substitute the last element of nums1 to the bigger number.

Solution (Python)

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        i = m - 1
        j = n - 1
        k = m + n - 1
        
        while i >= 0 and j >= 0:
            if nums1[i] < nums2[j]:
                nums1[k] = nums2[j]
                j = j - 1
            else:
                nums1[k] = nums1[i]
                i = i - 1
            k = k - 1
        
        if j >= 0:
            nums1[:k+1] = nums2[:j+1]
        
        return nums1
        

Result

Runtime: 24 ms
Memory Usage: 13.4 MB
Runtime Beats 73.13% of Python Submission

profile
if this then that

0개의 댓글