歸并算法之有序數(shù)組合并算法實(shí)現(xiàn)
歸并算法之有序數(shù)組合并算法實(shí)現(xiàn)
一個(gè)簡(jiǎn)單的有序數(shù)組合并算法：寫一個(gè)函數(shù)，傳入 2 個(gè)有序的整數(shù)數(shù)組，返回一個(gè)有序的整數(shù)數(shù)組。實(shí)現(xiàn)相當(dāng)簡(jiǎn)單，創(chuàng)建一個(gè)長(zhǎng)度為這兩個(gè)長(zhǎng)度之和的數(shù)組，然后分別用三個(gè)指針指向這三個(gè)數(shù)組，找到這兩個(gè)數(shù)組中各個(gè)元素在合并數(shù)組中的位置并插入，直到某個(gè)數(shù)組指針到達(dá)尾部。再將另一個(gè)數(shù)組剩下的所有元素，直接放入歸并數(shù)組尾部。算法的簡(jiǎn)單實(shí)現(xiàn)，需要注意的是對(duì)參數(shù)的校驗(yàn)，判斷數(shù)組是否有序。
public class MergeOrderedArray {
public static int[] merge(int [] a,int []b){
if(!isOrderedArray(a)){
System.out.println(" array a is not an ordered array.");
return null;
}
if(!isOrderedArray(b)){
System.out.println(" array b is not an ordered array.");
return null;
}
int a_len = a.length;
int b_len = b.length;
int[] merge = new int[a_len+b_len];
int i=0,j=0,k=0;
while(i<a_len&&j<b_len){
if(a[i]<b[j]){
merge[k++]=a[i++];
}else{
merge[k++]=b[j++];
}
}
//A數(shù)組全部合并完畢，將b數(shù)組剩余直接加入合并數(shù)組
if(i==a_len){
for(;j<b_len;j++){
merge[k++]= b[j];
}
}else{
for(;i<a_len;i++){
merge[k++]= a[i];
}
}
return merge;
}
public static boolean isOrderedArray(int [] array){
if(array==null||array.length==0){
return false;
}
for(int i = 0;i<array.length-1;i++){
if(array[i]>array[i+1]){
return false;
}
}
return true;
}
public static void main(String[] args) {
int a [] = {1,2,3,4,5};
int b [] = {2,3,4,5,6,7,8,9};
int [] merge = merge(a,b);
System.out.println(Arrays.toString(merge));
}
}
算法的時(shí)間復(fù)雜度，取決于待合并的兩個(gè)數(shù)組的長(zhǎng)度，所以是O(M+N)，空間復(fù)雜度也是O(M+N)，即需要的歸并數(shù)組的長(zhǎng)度是M+N。
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
這篇文章主要介紹了CORS跨域問(wèn)題常用解決方法代碼實(shí)例,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-11-11
Spring Boot的filter（過(guò)濾器）簡(jiǎn)單使用實(shí)例詳解
過(guò)濾器（Filter）的注冊(cè)方法和 Servlet 一樣，有兩種方式：代碼注冊(cè)或者注解注冊(cè)，下面通過(guò)實(shí)例給大家介紹Spring Boot的filter（過(guò)濾器）簡(jiǎn)單使用，一起看看吧2017-04-04
使用springboot aop記錄接口請(qǐng)求的參數(shù)及響應(yīng)
該文章介紹了如何使用SpringAOP的切面注解,如@Before和@AfterReturning,來(lái)記錄Controller層的方法輸入?yún)?shù)和響應(yīng)結(jié)果,還討論了@Around注解的靈活性,允許在方法執(zhí)行前后進(jìn)行更多控制,需要的朋友可以參考下2024-05-05
這篇文章主要介紹了SpringIOC BeanDeifition的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)springioc，感興趣的朋友可以了解下2020-12-12
SpringBoot環(huán)境Druid數(shù)據(jù)源使用及特點(diǎn)
Druid 是目前比較流行的高性能的，分布式列存儲(chǔ)的OLAP框架(具體來(lái)說(shuō)是MOLAP)。本文給大家分享SpringBoot環(huán)境Druid數(shù)據(jù)源使用及特點(diǎn)介紹，感興趣的朋友跟隨小編一起看看吧2021-07-07
Java服務(wù)剛啟動(dòng)時(shí)接口超時(shí)排查全過(guò)程
這篇文章主要為大家介紹了Java服務(wù)剛啟動(dòng)時(shí)，一小波接口超時(shí)排查全過(guò)程，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-07-07
本文主要介紹了淺談springBean的作用域，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
java實(shí)現(xiàn)發(fā)送郵箱驗(yàn)證碼
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)發(fā)送郵箱驗(yàn)證碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
java jni調(diào)用c函數(shù)實(shí)例分享(java調(diào)用c函數(shù))
Java代碼中調(diào)用C/C++代碼,當(dāng)然是使用JNI，JNI是Java native interface的簡(jiǎn)寫，可以譯作Java原生接口，下面看實(shí)例吧2013-12-12
本篇文章給大家詳細(xì)分享了關(guān)于Java異常的相關(guān)知識(shí)點(diǎn)，對(duì)此有需要的朋友跟著學(xué)習(xí)下吧。2018-05-05