LeetCode - 88. Merge Sorted Array

LeetCode - 88. Merge Sorted Array

Merge Sorted Array - LeetCode

 

 

88. Merge Sorted Array

You 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 final sorted array should not be returned by the function, 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.

 

Non-decreasing order = "같은 숫자가 있을 수 있는 오름차순"

 

처음에 문제를 이해하지 못해서 계속 nums1을 재정의해서 답안을 제출했더니 통과가 안됬다 ㅠㅠ

 

알고보니 nums1를 재정의하지않고 nums1의 원소를 변경하여 문제를 풀어야했다.

 

문제에서 m의 값은 nums1리스트의 원소의 총 개수 ,n의 값은 0의 개수라는 걸 이용해서

 

 

nums1의 0을 제거해주기 위해 n번 pop을 시행한 후 nums2의 수를 for문을 통해 num1으로 넘긴 뒤 정렬했다. 

 

 

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        for __ in range(n):
            nums1.pop()
        for i in nums2:
            nums1.append(i)
        nums1.sort()
        
        
      
 #sudocode
  def merge(self, nums1, m, nums2, n):
        for __ in range(0을 제외시켜야할 수 ):
            nums1.pop()
        for i in nums2:(nums2의 원소를 nums1에 추가해준다)
            nums1.append(num2의 원소)
        nums1.sort() (합쳐진 nums1의 원소들을 sort()함수를 통해 오름차순 정렬
        
        
 시간복잡도
 O(m+n)

 

 

LeetCode에서 제일 많은 투표를 받은 해결방법

class Solution(object):
    def merge(self, nums1, m, nums2, n):
      for j in range(n):
          nums1[m+j] = nums2[j]
      nums1.sort()
      
      
접근법: 두 포인터
각각 m-1과 n-1로 초기화된 두 개의 포인터 i와 j로 시작할 수 있습니다. 
또한 m+n-1로 초기화된 또 다른 포인터 k를 갖게 되며, 
이는 더 큰 요소를 배치할 nums1의 위치를 ​​추적하는 데 사용됩니다. 
그런 다음 배열 i와 j의 끝부터 반복을 시작하고 이 위치의 요소를 비교할 수 있습니다.
nums1의 더 큰 요소를 k 위치에 배치하고 이에 따라 해당 포인터 i 또는 j를 감소시킵니다. 
nums2의 모든 요소를 ​​반복할 때까지 이 작업을 계속할 것입니다. 
nums1에 아직 요소가 남아 있으면 해당 요소가 이미 올바른 위치에 있으므로 아무것도 할 필요가 없습니다.

복잡성
시간 복잡도: O(m+n)
두 배열을 한 번 반복하므로 시간 복잡도는 O(m+n)입니다.

공간 복잡도: O(1)
추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.