美團(tuán)一面：兩個(gè)有序的數(shù)組，如何高效合并成一個(gè)有序數(shù)組？

點(diǎn)擊關(guān)注公眾號(hào)，Java干貨及時(shí)送達(dá)??

在說這個(gè)題目之前先來說說一個(gè)排序算法 “歸并算法”

歸并算法采取思想是分治思想，分治思想簡(jiǎn)單說就是分而治之，將一個(gè)大問題分解為小問題，將小問題解答后合并為大問題的答案。

乍一看跟遞歸思想很像，確實(shí)如此，分治思想一般就是使用遞歸來實(shí)現(xiàn)的。但是需要注意的是：遞歸是代碼實(shí)現(xiàn)的方式，分治屬于理論。另外，數(shù)據(jù)結(jié)構(gòu)和算法系列面試題和答案全部整理好了，微信搜索Java技術(shù)棧，在后臺(tái)發(fā)送：面試，可以在線閱讀。

接下來看一副圖理解下：

說完它的思想：我們?cè)賮矸治鱿聲r(shí)間復(fù)雜度。歸并算法采用的是完全二叉樹的形式。所以可以由完全二叉樹的深度可以得知，整個(gè)歸并排序需要進(jìn)行l(wèi)og2n次。

然后每一次需要消耗O{n}時(shí)間。所以總的時(shí)間復(fù)雜度為o{nlog2n}。歸并排序是一種比較占用內(nèi)存，但是效率高且穩(wěn)定的算法。

貼上代碼：

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?????{
????????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;
????//進(jìn)行比較。注意這里++是后執(zhí)行的，先取出來數(shù)組中的值然后++
????while?(start1?<=?end1?&&?start2?<=?end2)
????????result[k++]?=?arr[start1]?????//將每個(gè)分組剩余的進(jìn)行復(fù)制
????while?(start1?<=?end1)?
????????result[k++]?=?arr[start1++];
????//將每個(gè)分組剩余的進(jìn)行復(fù)制
????while?(start2?<=?end2)
????????result[k++]?=?arr[start2++];?
????for?(k?=?start;?k?<=?end;?k++)
????????arr[k]?=?result[k];
????return?result;
}

說完了歸并算法回到題目上來 首先分析下 題目給定的是兩個(gè)已經(jīng)排好序的數(shù)組合并，關(guān)鍵字“合并”，“兩個(gè)”，正好符合我們的歸并算法，并且已經(jīng)分類好了，只需要去合并就可以了。

來看下幾張圖。

藍(lán)色的箭頭表示最終選擇的位置，而紅色的箭頭表示兩個(gè)數(shù)組當(dāng)前要比較的元素，比如當(dāng)前是2與1比較，1比2小，所以1放到藍(lán)色的箭頭中，藍(lán)色的箭頭后移，1的箭頭后移。

然后2與4比較，2比4小那么2到藍(lán)色的箭頭中，藍(lán)色箭頭后移，2后移，繼續(xù)比較.......

歸并思路就是這樣了，最后唯一需要注意的是那個(gè)先比較完的話，那么剩下的直接不需要比較，把后面的直接移上去就可以了，這個(gè)需要提前判定一下。另外，數(shù)據(jù)結(jié)構(gòu)系列面試題和答案全部整理好了，微信搜索Java技術(shù)棧，在后臺(tái)發(fā)送：面試，可以在線閱讀。

貼上代碼：

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?????{
????????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?????{
????????if?(arr1[i]?????????{

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

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

????while?(i?????????newArr[k++]?=?arr1[i++];
????while?(j?????????newArr[j++]?=?arr2[j++];
????return?newArr;
}

最后感謝一下大佬提供的思路：

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

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

版權(quán)聲明：本文為CSDN博主「貂蟬要睡覺」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接及本聲明。

（完）

?關(guān)注公眾號(hào)：Java后端編程，回復(fù)下面關(guān)鍵字?
要Java學(xué)習(xí)完整路線，回復(fù)??路線?
缺Java入門視頻，回復(fù)：?視頻?
要Java面試經(jīng)驗(yàn)，回復(fù)??面試?
缺Java項(xiàng)目，回復(fù)：?項(xiàng)目?
進(jìn)Java粉絲群：?加群?

PS：如果覺得我的分享不錯(cuò)，歡迎大家隨手點(diǎn)贊、在看。
（完）




加我"微信"?獲取一份 最新Java面試題資料
請(qǐng)備注：666，不然不通過～

最近好文

1、強(qiáng)烈不建議你用 a.equals(b) 判斷對(duì)象相等！
2、如何優(yōu)雅的寫出你的SQL語句？
3、10000 字講清楚 Spring Boot 注解原理
4、13個(gè)優(yōu)秀的 Vue 開源項(xiàng)目及合集推薦
5、Java程序短信驗(yàn)證碼最佳實(shí)踐


最近面試BAT，整理一份面試資料《Java面試BAT通關(guān)手冊(cè)》，覆蓋了Java核心技術(shù)、JVM、Java并發(fā)、SSM、微服務(wù)、數(shù)據(jù)庫、數(shù)據(jù)結(jié)構(gòu)等等。
獲取方式：關(guān)注公眾號(hào)并回復(fù)?java?領(lǐng)取，更多內(nèi)容陸續(xù)奉上。
明天見(??ω??)??