[Sorting and Searching] interview questions #1

[rygh4775]

Sorted Merge: You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

[RoyMoon]

솔루션 : A배열에 tail 인덱스를 정해서 가장 큰 수부터 tail 부분에 복사 한다.

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
      int tail = m + n - 1;
      m--;
      n--;
      while(n >=0) {
        if(m >= 0 && nums1[m] >= nums2[n]) {
          nums1[tail--] = nums1[m--];
        } else {
          nums1[tail--] = nums2[n--];
        }
      }
    }

시간 복잡도 O(m+n)