LeetCode-88 Merge sort array

Merge Sorted Array - LeetCode

 
처음 문제를 보았을 때 nums2의 각 요소들을 키 값으로 하고 nums1을 배열로 하여 이진 탐색을 통해 해결할 수 있다고 생각했습니다. 애초에 주어진 배열이 오름차순으로 정렬되어 있고, 키를 가지고 탐색에 성공했다면 nums1에 이미 nums2의 요소와 같은 값이 있다는 의미이기에 해당 인덱스 뒤에 키 값을 위치 시켜주면 됩니다. 만약 찾지 못했다면 탐색을 실패한 위치가 해당 키 값이 위치할 인덱스가 될 것입니다. 하지만 이 방법은 시간 초과로 실패하였습니다.
 

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        for element in nums2:
            start = 0
            end = len(nums1) - 1

            while start <= end:
                mid = (start + end) // 2

                if nums1[mid] == element:
                    tmp = [element]
                    nums1 = nums1[:mid] + tmp + nums1[mid:]
                elif nums1[mid] < element:
                    start = mid + 1
                else:
                    end = mid - 1
            if (nums1[mid]>element):
                tmp = [element]
                nums1 = nums1[:mid] + tmp + nums1[mid:]
            else:
                tmp = [element]
                nums1 = nums1[:mid+1] + tmp + nums1[mid+1:]

두번째 방법은 조금 더 쉬운 방법입니다. nums1 배열을 nums1의 m의 크기만큼을 제외하고 뒷부분은 잘라 줍니다. nums1뒤에 마찬가지로 n의 크기만큼의 nums2를 붙여준 후 sort를 통해 정렬할 수 있습니다.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
     
        del nums1[m:]
        nums1 += nums2[0:n]
        nums1.sort()