美团一面:两个有序的数组,如何高效合并成一个有序数组?

互联网架构师

共 976字,需浏览 2分钟

 ·

2021-10-24 17:30

点击关注公众号,回复“2T”获取2TB学习资源!
互联网架构师后台回复 2T 有特别礼包
上一篇:深夜看了张一鸣的微博,让我越想越后怕

在说这个题目之前先来说说一个排序算法 “归并算法

归并算法采取思想是分治思想,分治思想简单说就是分而治之,将一个大问题分解为小问题,将小问题解答后合并为大问题的答案。

乍一看跟递归思想很像,确实如此,分治思想一般就是使用递归来实现的。但是需要注意的是:递归是代码实现的方式,分治属于理论。另外,数据结构和算法系列面试题和答案全部整理好了,微信搜索互联网架构师,在后台发送:2T,可以在线阅读。

接下来看一副图理解下:

说完它的思想:我们再来分析下时间复杂度。归并算法采用的是完全二叉树的形式。所以可以由完全二叉树的深度可以得知,整个归并排序需要进行log2n次。

然后每一次需要消耗O{n}时间。所以总的时间复杂度为o{nlog2n}。归并排序是一种比较占用内存,但是效率高且稳定的算法。

贴上代码:

static void Main(string[] args) {
    int[] arr = new int[] { 14,12,15,13,11,16 ,10};

    int[] newArr = Sort(arr, new int[7], 0, arr.Length - 1);
    for (int i = 0; i < newArr.Length - 1; i++)
    {
        Console.WriteLine(newArr[i]);
    }

    Console.ReadKey();
}

public static int[] Sort(int[] arr, int[] result, int start, int end)
{
    if (start >= end)
        return null;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    Sort(arr, result, start1, end1);
    Sort(arr, result, start2, end2);
    int k = start;
    //进行比较。注意这里++是后执行的,先取出来数组中的值然后++
    while (start1 <= end1 && start2 <= end2)
        result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    //将每个分组剩余的进行复制
    while (start1 <= end1) 
        result[k++] = arr[start1++];
    //将每个分组剩余的进行复制
    while (start2 <= end2)
        result[k++] = arr[start2++]; 
    for (k = start; k <= end; k++)
        arr[k] = result[k];
    return result;
}
说完了归并算法回到题目上来 首先分析下 题目给定的是两个已经排好序的数组合并,关键字“合并”,“两个”,正好符合我们的归并算法,并且已经分类好了,只需要去合并就可以了。

来看下几张图。

蓝色的箭头表示最终选择的位置,而红色的箭头表示两个数组当前要比较的元素,比如当前是2与1比较,1比2小,所以1放到蓝色的箭头中,蓝色的箭头后移,1的箭头后移。

然后2与4比较,2比4小那么2到蓝色的箭头中,蓝色箭头后移,2后移,继续比较.......
归并思路就是这样了,最后唯一需要注意的是那个先比较完的话,那么剩下的直接不需要比较,把后面的直接移上去就可以了,这个需要提前判定一下。另外,数据结构系列面试题和答案全部整理好了,微信搜索互联网架构师,在后台发送:2T,可以免费获取。
贴上代码:
static void Main(string[] args) {
    int[] arr1 = new int[] { 2, 3, 6, 8 };
    int[] arr2 = new int[] { 1, 4, 5, 7 };
    int[] newArr = Sort(arr1, arr2);
    for (int i = 0; i < newArr.Length - 1; i++)
    {
        Console.WriteLine(newArr[i]);
    }

    Console.ReadKey();
}

public static int[] Sort(int[] arr1,int[] arr2)
{
    int[] newArr = new int[arr1.Length + arr2.Length];
    int i = 0, j = 0, k = 0;
    while (i < arr1.Length && j < arr2.Length)
    {
        if (arr1[i] < arr2[j])
        {

            newArr[k] = arr1[i];
            i++;
            k++;
        }
        else
        {

            newArr[k] = arr2[j];
            j++;
            k++;
        }
    }

    while (i < arr1.Length)
        newArr[k++] = arr1[i++];
    while (j < arr2.Length)
        newArr[j++] = arr2[j++];
    return newArr;
}
最后感谢一下大佬提供的思路:

https://blog.csdn.net/k_koris/article/details/80508543

原文链接:https://blog.csdn.net/weixin_40097554/article/details/108656165/


感谢您的阅读,也欢迎您发表关于这篇文章的任何建议,关注我,技术不迷茫!小编到你上高速。

    · END ·
最后,关注公众号互联网架构师,在后台回复:2T,可以获取我整理的 Java 系列面试题和答案,非常齐全


正文结束


推荐阅读 ↓↓↓

1.不认命,从10年流水线工人,到谷歌上班的程序媛,一位湖南妹子的励志故事

2.如何才能成为优秀的架构师?

3.从零开始搭建创业公司后台技术栈

4.程序员一般可以从什么平台接私活?

5.37岁程序员被裁,120天没找到工作,无奈去小公司,结果懵了...

6.IntelliJ IDEA 2019.3 首个最新访问版本发布,新特性抢先看

7.这封“领导痛批95后下属”的邮件,句句扎心!

8.15张图看懂瞎忙和高效的区别!

浏览 21
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报