Merge Sort 예제로 살펴보자.
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.
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]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].
Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
Constraints:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[j] <= 10^9
Follow up: Can you come up with an algorithm that runs in O(m + n) time?
이 문제를 해결하기 위해서 사용해야할 시간복잡도를 얼마나 가져가야할까?
알고리즘 문제에서 요구하는 최대의 값을 10^9으로 잡곤한다.
10^9는 1,000,000,000으로 십억이다.
백억건을 처리하기위해서는 알고리즘 효율에 따라 처리하는 속도가 천차만별이다.
이 문제 제약사항을 다시한번 살펴보면 num1[i] 와 num2[j]의 값은 최소 -10억 ~ +10억 으로 int형을 임을 명시해줬다.
입력 사이즈를 5,000건을 정렬한다고 했을 때 아래와 같은 결과를 얻을 수 있었다.
아래 코드는 O((m+n) log (m+n))의 시간복잡도를 가진다.
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int index = 0;
for(int i = m; i <= nums1.length - 1; i++) {
nums1[i] = nums2[index++];
}
Arrays.sort(nums1);
}
}
알고리즘을 구어로 작성해보면
num2의 원소를 num1의 뒷부분에 빈 공간에 복사를 하고
num1의 배열 전체를 정렬한다.
num1의 크기가 m+n으로 구성되어있음으로,