最近開始刷LintCode上的題目，先從標簽為容易的開始刷。今天刷的這兩題目差不多為同一類型的題目，都是為按照一定的規則合并兩個已經有序的數組。

　　

[Q6]

描述：

　　合并兩個排序的整數數組A和B變成一個新的數組。

　　樣例：

　　給出A=[1,2,3,4]，B=[2,4,5,6]，返回?[1,2,2,3,4,4,5,6]

思路：

　　題目的方法原型為：

1 public int[] mergeSortedArray(int[] A, int[] B) {}

　　所以即從A和B數組中一次取數比較大小，將其中較小者放入新的數組C。

　　當其中一個數組已經全部取出，則將剩余一個數組中的數全部放入數組C中。

　　在歸并排序中，當把一個序列分解為若干個子序列之后，正是通過遞歸的合并子序列來完成排序。

實現：

?

1 public int[] mergeSortedArray(int[] A, int[] B) { 2 // Write your code here 3 4 int[] C = new int[A.length + B.length]; 5 6 int indexa = 0; //表示a數組的索引位置 7 int indexb = 0; //表示b數組的索引位置 8 int indexc = 0; //表示c數組的索引位置 9 10 //當某個數組已經全部合并進新的數組的時候跳出循環 11 while( ! ((indexa == A.length) || (indexb == B.length))){ 12 if(A[indexa] <= B[indexb]){ 13 C[indexc ++] = A[indexa ++]; 14 } 15 else{ 16 C[indexc ++] = B[indexb ++]; 17 18 } 19 } 20 //A數組還有剩余元素 21 while(indexa < A.length){ 22 C[indexc ++] = A[indexa ++]; 23 } 24 //B數組還有剩余元素 25 while(indexb < B.length){ 26 C[indexc ++] = B[indexb ++]; 27 } 28 29 return C; 30 31 }

?

[Q64]

描述：

　　合并兩個排序的整數數組A和B變成一個新的數組。

　　你可以假設A具有足夠的空間（A數組的大小大于或等于m+n）去添加B中的元素。

　　樣例：

　　給出 A =?[1, 2, 3, empty, empty], B =?[4, 5]

　　合并之后 A 將變成?[1,2,3,4,5]

思路：

　　題目的方法原型為：

1 public void mergeSortedArray(int[] A, int m, int[] B, int n) {}

?

　　從題目函數原型和題目描述可以看出，這次在合并的時候是在A數組的基礎上進行合并，A數組的大小大于或等于A+B的大小，所以可以將B數組合并到A數組中。

　　考慮兩種情況：

　　1 當B中的某個元素已經比A中的最后一個元素還要大時，此時不需要再繼續比較了，直接將B中包括當前元素的剩余元素全部插入到A數組最后。

　　2 當B中的第x元素通過比較插入到了A數組的y位置上，則第x + 1 元素直接從y + 1 位置開始繼續比較，前面的無需比較。

　　此題目比上面的題目還要多增加一個步驟，因為是在A數組上進行插入，所以插入之后，插入位置以后的元素需要往后移動一個位置，涉及到一個移動操作。

實現：

1 public void mergeSortedArray(int[] A, int m, int[] B, int n) { 2 int indexa = 0 ; // 標識A數組的遍歷位置 3 int indexb = 0 ; //標識B數組的遍歷位置 4 int lastIndex = m - 1 ; //標識A數組中最后的位置 5 6 while ( (indexa <= lastIndex) && (indexb <= n - 1) ) { 7 if(B[indexb] < A[indexa]){ 8 //這個題目第一此提交出現了錯誤， 錯誤原因是下面的for循環中應該是i -- , 手滑寫成了 i ++ 9 for(int i = lastIndex ; i >= indexa ; i --){ 10 A[i + 1] = A [i] ; 11 } 12 A[indexa ++] = B[indexb ++]; 13 lastIndex ++ ; 14 } 15 else{ 16 indexa ++ ; 17 } 18 } 19 while(indexb <= n - 1 ) { 20 A[++ lastIndex] = B[indexb ++] ; 21 } 22 }

?

總結：

　　有關于數組的操作，大多可以用過設置不同變量，來標識數組中的不同位置，從而可以進行不同的操作。

?

轉載于:https://www.cnblogs.com/tancky/p/6574747.html

總結

以上是生活随笔為你收集整理的【LintCode题集】Q6、Q64的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。