卖萌的弱渣

I am stupid, I am hungry.

Merge Sorted Array

Merge Sorted Array

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

Example

A = [1, 2, 3, empty, empty], B = [4, 5]

After merge, A will be filled as [1, 2, 3, 4, 5]

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 and n respectively.

Solution

  • Time: O(N), Space: O(1)
  • Tranverse A and B from the end
  • index: index of the result
  • i: index of A
  • j: index of B
(Merge-Sorted-Array.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    """
    @param A: sorted integer array A which has m elements, 
              but size of A is m+n
    @param B: sorted integer array B which has n elements
    @return: void
    """
    def mergeSortedArray(self, A, m, B, n):
        # write your code here
        if n == 0:
            return
        index = m+n-1
        i = m-1
        j = n-1
        while i>=0 and j>=0:
            if A[i] >= B[j]:
                A[index] = A[i]
                i -= 1
                index -= 1
            else:
                A[index] = B[j]
                j -= 1
                index -= 1
        while j>=0:
            A[index] = B[j]
            j -= 1
            index -= 1
        return