美團(tuán)一面：兩個有序的數(shù)組，如何高效合并成一個有序數(shù)組？
點擊關(guān)注公眾號，利用碎片時間學(xué)習(xí)
在說這個題目之前先來說說一個排序算法 “歸并算法”
歸并算法采取思想是分治思想，分治思想簡單說就是分而治之，將一個大問題分解為小問題，將小問題解答后合并為大問題的答案。
乍一看跟遞歸思想很像，確實如此，分治思想一般就是使用遞歸來實現(xiàn)的。但是需要注意的是：遞歸是代碼實現(xiàn)的方式，分治屬于理論。
接下來看一副圖理解下：
說完它的思想：我們再來分析下時間復(fù)雜度。歸并算法采用的是完全二叉樹的形式。所以可以由完全二叉樹的深度可以得知，整個歸并排序需要進(jìn)行l(wèi)og2n次。
然后每一次需要消耗O{n}時間。所以總的時間復(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]?????//將每個分組剩余的進(jìn)行復(fù)制
????while?(start1?<=?end1)?
????????result[k++]?=?arr[start1++];
????//將每個分組剩余的進(jìn)行復(fù)制
????while?(start2?<=?end2)
????????result[k++]?=?arr[start2++];?
????for?(k?=?start;?k?<=?end;?k++)
????????arr[k]?=?result[k];
????return?result;
}
說完了歸并算法回到題目上來 首先分析下 題目給定的是兩個已經(jīng)排好序的數(shù)組合并，關(guān)鍵字“合并”，“兩個”，正好符合我們的歸并算法，并且已經(jīng)分類好了，只需要去合并就可以了。
來看下幾張圖。
藍(lán)色的箭頭表示最終選擇的位置，而紅色的箭頭表示兩個數(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ù)比較.......
歸并思路就是這樣了，最后唯一需要注意的是那個先比較完的話，那么剩下的直接不需要比較，把后面的直接移上去就可以了，這個需要提前判定一下。
貼上代碼：
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)載請附上原文出處鏈接及本聲明。
最近面試BAT，整理一份面試資料《Java面試BATJ通關(guān)手冊》，覆蓋了Java核心技術(shù)、JVM、Java并發(fā)、SSM、微服務(wù)、數(shù)據(jù)庫、數(shù)據(jù)結(jié)構(gòu)等等。
獲取方式：點“在看”，關(guān)注公眾號并回復(fù)?Java?領(lǐng)取，更多內(nèi)容陸續(xù)奉上。
文章有幫助的話，在看，轉(zhuǎn)發(fā)吧。
謝謝支持喲 (*^
