Merge Sorted Array

Question

  1. Given two sorted integer arrays A and B, merge B into A as one sorted array.
  2. Example
  3. A = [1, 2, 3, empty, empty], B = [4, 5]
  4. After merge, A will be filled as [1, 2, 3, 4, 5]
  5. Note
  6. You may assume that A has enough space (size that is greater or equal to m + n)
  7. to hold additional elements from B.
  8. The number of elements initialized in A and B are m and n respectively.

題解

因為本題有 in-place 的限制,故必須從陣列末尾的兩個元素開始比較;否則就會產生挪動,一旦挪動就會是 O(n^2) 的。
自尾部向首部逐個比較兩個陣列內的元素,取較大的置於陣列 A 中。由於 A 的容量較 B 大,故最後 m == 0 或者 n == 0 時僅需處理 B 中的元素,因為 A 中的元素已經在 A 中,無需處理。

Python

  1. class Solution:
  2. """
  3. @param A: sorted integer array A which has m elements,
  4. but size of A is m+n
  5. @param B: sorted integer array B which has n elements
  6. @return: void
  7. """
  8. def mergeSortedArray(self, A, m, B, n):
  9. if B is None:
  10. return A
  11. index = m + n - 1
  12. while m > 0 and n > 0:
  13. if A[m - 1] > B[n - 1]:
  14. A[index] = A[m - 1]
  15. m -= 1
  16. else:
  17. A[index] = B[n - 1]
  18. n -= 1
  19. index -= 1
  20. # B has elements left
  21. while n > 0:
  22. A[index] = B[n - 1]
  23. n -= 1
  24. index -= 1

C++

  1. class Solution {
  2. public:
  3. /**
  4. * @param A: sorted integer array A which has m elements,
  5. * but size of A is m+n
  6. * @param B: sorted integer array B which has n elements
  7. * @return: void
  8. */
  9. void mergeSortedArray(int A[], int m, int B[], int n) {
  10. int index = m + n - 1;
  11. while (m > 0 && n > 0) {
  12. if (A[m - 1] > B[n - 1]) {
  13. A[index] = A[m - 1];
  14. --m;
  15. } else {
  16. A[index] = B[n - 1];
  17. --n;
  18. }
  19. --index;
  20. }
  21. // B has elements left
  22. while (n > 0) {
  23. A[index] = B[n - 1];
  24. --n;
  25. --index;
  26. }
  27. }
  28. };

Java

  1. class Solution {
  2. /**
  3. * @param A: sorted integer array A which has m elements,
  4. * but size of A is m+n
  5. * @param B: sorted integer array B which has n elements
  6. * @return: void
  7. */
  8. public void mergeSortedArray(int[] A, int m, int[] B, int n) {
  9. if (A == null || B == null) return;
  10. int index = m + n - 1;
  11. while (m > 0 && n > 0) {
  12. if (A[m - 1] > B[n - 1]) {
  13. A[index] = A[m - 1];
  14. m--;
  15. } else {
  16. A[index] = B[n - 1];
  17. n--;
  18. }
  19. index--;
  20. }
  21. // B has elements left
  22. while (n > 0) {
  23. A[index] = B[n - 1];
  24. n--;
  25. index--;
  26. }
  27. }
  28. }

源碼分析

第一個 while 只能用條件與(conditional AND)。

複雜度分析

最壞情況下需要遍歷兩個陣列中所有元素,時間複雜度為 O(n). 空間複雜度 O(1).