歸并算法之有序數(shù)組合并算法實(shí)現(xiàn)
更新時(shí)間：2017年07月03日 09:49:34 投稿：lqh
這篇文章主要介紹了歸并算法之有序數(shù)組合并算法實(shí)現(xiàn)的相關(guā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)文章
在安卓系統(tǒng)中插入表情到光標(biāo)位置的代碼詳解
這篇文章主要介紹了在安卓系統(tǒng)中插入表情到光標(biāo)位置的代碼詳解,利用Java代碼在EditText控件中實(shí)現(xiàn),需要的朋友可以參考下2015-07-07
Spring?Cloud?Gateway?是一個(gè)用于構(gòu)建?API?網(wǎng)關(guān)的框架,提供了多種服務(wù)路由、過濾和負(fù)載均衡的功能,這篇文章主要介紹了Java?Nacos與Gateway的使用操作筆記,需要的朋友可以參考下2024-08-08
這篇文章主要介紹了Spring自定義注解配置簡(jiǎn)單日志示例,注解可以增強(qiáng)我們的java代碼，同時(shí)利用反射技術(shù)可以擴(kuò)充實(shí)現(xiàn)很多功能,它們被廣泛應(yīng)用于三大框架底層,需要的朋友可以參考下2023-05-05
ShardingSphere JDBC強(qiáng)制路由使用的項(xiàng)目實(shí)踐
在某些特定場(chǎng)景下,可能需要繞過分片規(guī)則直接定位到特定的數(shù)據(jù)庫或表,這種情況下就可以使用HintRouting,本文就來介紹一下ShardingSphere JDBC強(qiáng)制路由使用的項(xiàng)目實(shí)踐,感興趣的可以了解一下2024-06-06
Java開發(fā)環(huán)境不再需要配置classpath問題
這篇文章主要介紹了Java開發(fā)環(huán)境不再需要配置classpath問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-12-12
java教程之對(duì)象序列化使用基礎(chǔ)示例詳解
所謂對(duì)象序列化就是將對(duì)象的狀態(tài)轉(zhuǎn)換成字節(jié)流，以后可以通過這些值再生成相同狀態(tài)的對(duì)象，下面詳細(xì)介紹一下java對(duì)象的序列化使用方法2014-01-01
這篇文章主要介紹了Java?批量生成條碼的示例代碼,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-08-08
Java中ResultSetMetaData 元數(shù)據(jù)的具體使用
本文主要介紹了Java中ResultSetMetaData 元數(shù)據(jù)的具體使用，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
AOP 從功能的角度來講，可能看作OOP編程方式的一種補(bǔ)充，提供了一種不同的代碼或者系統(tǒng)組織方式，下面這篇文章主要給大家介紹了關(guān)于Spring學(xué)習(xí)教程之AOP模塊的相關(guān)資料，文中通過圖文介紹的非常詳細(xì)，需要的朋友可以參考下2018-05-05
本篇文章是對(duì)java垃圾回收進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-06-06