将几个递增数组合并为排序数组

题目

这是一道面试题，题目如下：

合并 3 个递增数组A=[2,3,4,5,6,9,10], B=[6,9,10,11,13,15], C=[2,3,4,7,9,10],输出到D. 要求:

1. D的每个元素也是递增(a1 <= a2) 不用去重)
2. 不使用 api 和排序方法.
3. 时间复杂度 O(n),空间复杂度为 O(1)。

代码

本示例使用 C# 实现,完整的代码，可以拿来即用

namespace sortDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] aArry = new int[] { 2, 3, 4, 5, 6, 9, 10 };
            int[] bArry = new int[] { 6, 9, 10, 11, 13, 15 };
            int[] cArry = new int[] { 2, 3, 4, 7, 9, 10 };
            // 申请一个数组e
            int[] eArry = Merge(bArry, cArry);
            int[] dArry = MergeT(aArry, eArry);
            for (int k = 0; k < dArry.Length; k++)
            {
                System.Console.WriteLine(dArry[k]);
            }
        }
        /// <summary>
        ///  融合两个数组，并排序
        /// </summary>
        /// <param name="a">数组a</param>
        /// <param name="b">数组b</param>
        /// <returns></returns>
        public static int[] Merge(int[] a, int[] b)
        {
            int[] answer = new int[a.Length + b.Length];
            int i = 0, j = 0, k = 0;
            while (i < a.Length && j < b.Length)
                answer[k++] = a[i] < b[j] ? a[i++] : b[j++];
            while (i < a.Length)
                answer[k++] = a[i++];
            while (j < b.Length)
                answer[k++] = b[j++];
            return answer;
        }
        /// <summary>
        /// 和上一个类似，代码比较紧凑
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static int[] MergeT(int[] a, int[] b)
        {
            int[] answer = new int[a.Length + b.Length];
            int i = a.Length - 1, j = b.Length - 1, k = answer.Length;
            while (k > 0)
                answer[--k] =
                        (j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
            return answer;
        }
    }
}

关于时间复杂度和空间复杂度参考：

语雀内容