题目10

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例:
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sorted-merge-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution 
{
    public void merge(int[] A, int m, int[] B, int n) 
    {
        int i = 0;
        int j = 0;
        int k = 0;
        int[] C = new int[m+n];
        while(i < m && j < n)
        {
            if(A[i] < B[j]) 
            {
                C[k] = A[i];
                k++;
                i++;
            }
            else if(A[i] > B[j]) 
            {
                C[k] = B[j];
                k++;
                j++;
            }
            else
            {
                C[k] = A[i];
                C[k+1] = A[i];
                k++;k++;
                i++;
                j++;
            }
        }

        while(i < m)
        {
            C[k] = A[i];
            k++;
            i++;
        }

        while(j < n)
        {
            C[k] = B[j];
            k++;
            j++;
        }

        for(int p = 0;p < m+n;p++)
        {
            A[p] = C[p];
        }
    }
}
//时间复杂度：O(m+n)
//空间复杂度：O(m+n)
//几个if放在一起，所有if的条件都会判断一遍，有可能判断的时候会出错，所以要用if...else if...else

class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify A in-place instead.
        """
        A[m:] = B
        A.sort()
//时间复杂度：O((m+n)log⁡(m+n))，排序序列长度为 m+n，套用快速排序的时间复杂度即可。

//空间复杂度：O(log(m+n))，排序序列长度为 m+n，套用快速排序的空间复杂度即可。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sorted-merge-lcci/solution/mian-shi-ti-1001-he-bing-pai-xu-de-shu-zu-by-leetc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify A in-place instead.
        """
        pa, pb = m - 1, n - 1
        tail = m + n - 1
        while pa >= 0 or pb >= 0:
            if pa == -1:
                A[tail] = B[pb]
                pb -= 1
            elif pb == -1:
                A[tail] = A[pa]
                pa -= 1
            elif A[pa] > B[pb]:
                A[tail] = A[pa]
                pa -= 1
            else:
                A[tail] = B[pb]
                pb -= 1
            tail -= 1


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sorted-merge-lcci/solution/mian-shi-ti-1001-he-bing-pai-xu-de-shu-zu-by-leetc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。