Sorting and Searching - Top Interview Questions[EASY] (5/9) : Python

88. Merge Sorted Array

Easy

32104857Add to ListShare

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

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 equal to m + n) to hold additional elements from nums2.

Example 1:

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

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1]

Constraints:

0 <= n, m <= 200
1 <= n + m <= 200
nums1.length == m + n
nums2.length == n
-109 <= nums1[i], nums2[i] <= 109

leetcode.com/problems/merge-sorted-array/

3번 방법이 가장 효율적이지만 API 사용법 알아보기 위해, 1번 2번도 살펴봄

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        nums1[:] = sorted(nums1[:m] + nums2)

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        # Make a copy of nums1.
        nums1_copy = nums1[:m] 
        nums1[:] = []

        # Two get pointers for nums1_copy and nums2.
        p1 = 0 
        p2 = 0
        
        # Compare elements from nums1_copy and nums2
        # and add the smallest one into nums1.
        while p1 < m and p2 < n: 
            if nums1_copy[p1] < nums2[p2]: 
                nums1.append(nums1_copy[p1])
                p1 += 1
            else:
                nums1.append(nums2[p2])
                p2 += 1

        # if there are still elements to add
        if p1 < m: 
            nums1[p1 + p2:] = nums1_copy[p1:]
        if p2 < n:
            nums1[p1 + p2:] = nums2[p2:]

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        # two get pointers for nums1 and nums2
        p1 = m - 1
        p2 = n - 1
        # set pointer for nums1
        p = m + n - 1
        
        # while there are still elements to compare
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] < nums2[p2]:
                nums1[p] = nums2[p2]
                p2 -= 1
            else:
                nums1[p] =  nums1[p1]
                p1 -= 1
            p -= 1
        
        # add missing elements from nums2
        nums1[:p2 + 1] = nums2[:p2 + 1]

leetcode.com/problems/first-bad-version/

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """        
        left = 1
        right = n
        while left < right:
            mid = left + (right - left)//2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

리트코드 코딩 인터뷰 문제 목록(EASY) - Java

Array - Top Interview Questions[EASY] (1/9) : Java

String - Top Interview Questions[EASY] (2/9) : Java

Linked List - Top Interview Questions[EASY] (3/9) : Java

Trees - Top Interview Questions[EASY] (4/9) : Java

Sorting and Searching - Top Interview Questions[EASY] (5/9) : Java

Dynamic Programming - Top Interview Questions[EASY] (6/9) : Java

Design - Top Interview Questions[EASY] (7/9) - Java

Math - Top Interview Questions[EASY] (8/9) - Java

Others - Top Interview Questions(EASY) - (9/9) : Java

리트코드 코딩 인터뷰 문제 목록(EASY) - Python

Array - Top Interview Questions[EASY] (1/9) : Python