[LeetCode] Merge Sorted Array

문제

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]

 

Approach

제일 간단한 방법은 array하나 더 만들어서 두 원소간 비교하며 오름차순으로 정렬하고

nums1 = (새로운 array)하는 것이지만

뭔가 반칙같아 이분탐색으로 nums2의 숫자가 nums1에 들어갈 자리를 찾은 후 끼워넣는 방식으로 해결했다.

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_MergeSortedArray.cpp

chi3236/algorithm