[OJ.leetcode] merge-sorted-array

https://oj.leetcode.com/problems/merge-sorted-array/

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m andn respectively.

/* 간단히 O(m+n) 알고리즘으로 해결하자면, mergesort에서 merge 알고리즘과 같이 하나씩 비교해서 채워나가고, 2개의 배열중 하나라도 끝까지 다 traversal 하면, 나머지 배열을 자동으로 끝까지 채워넣는 방식으로 해결 가능. 핵심은 A배열 뒷 공간의 index를 자유자재로 bug없이 활용할 수 있는지 여부 해볼 수 있는 사전 질문 정렬 방향은? 오름차순인지 내림차순인지? 중복된 숫자가 존재하는지, unique한지? 목표 : 한번에 accepted 받기 결과 : runtime error-> A배열의 뒤에서부터 A,B 모두 새로 정렬해서 넣는다고 단순하게 생각함; A배열 뒤에서부터 큰 것 순서대로 넣는 알고리즘으로 가야함. 3번 시도 후에 accepted( index >= 0 인지, index >0 인지 잘 생각해야 함) */ class Solution { public: void merge(int A[], int m, int B[], int n) { int i = m-1; int j = n-1; int index = m+n-1; while(i >= 0 && j >= 0) { if(A[i] > B[j]) { A[index--] = A[i--]; } else { A[index--] = B[j--]; } } while(i >= 0) { A[index--] = A[i--]; } while(j >= 0) { A[index--] = B[j--]; } } };