合併不等長的排序數組

Question

我有一個項目，需要我合併兩個排序數組（a和b），並將結果放入一個長度爲a.length + b.length的新數組中。 我正在跟蹤我的位置在所有3個數組中的計數器，並且我的數組長度不相等。我的約定是，如果一個數組在另一個之前耗盡，代碼會將其他數組的其餘部分轉儲到結果數組中。

不幸的是，我可以檢查其他數組是否仍包含元素的唯一方法是for循環。

任何人都可以幫助我嗎？這應該是一個相對簡單的解決方案，但我想不出一個解決方案。

public class Two { 
    public static void main(String[] args) { 
     //sample problem 
     int[] var_a = {2,3,5,5,8,10,11,17,18,20}; 
     int[] var_b = {5,6,7,8,14,15,17}; 
     final int a_size = 10; 
     final int b_size = 7; 
     final int c_size = 17; 
     int[] var_c = new int[17]; 

     int aCount = 0; 
     int bCount = 0; 
     int cCount = 0; 
     for (cCount = 0; cCount < c_size; cCount++) { 
      //b runs out before a runs out 
      if ((bCount == b_size) && (aCount <= a_size)) { 
       //dump rest of var_a into var_c  
       var_c[cCount] = var_a[aCount]; 
       aCount++; 
      } 
      //PROBLEM: bCount is equal to bSize, and is triggering the break. 
      //a runs out before b runs out 
      else if ((aCount == a_size) && (bCount <= b_size)) { 
       //dump rest of var_b into var_c 
       var_c[cCount] = var_b[bCount]; 
       bCount++; 
      } 

      if ((aCount >= a_size) || (bCount >= b_size) || (cCount >= c_size)) {break;} 

      if (var_a[aCount] < var_b[bCount]) { 
       var_c[cCount] = var_a[aCount]; 
       aCount++; 
      } else if (var_a[aCount] > var_b[bCount]) { 
       var_c[cCount] = var_b[bCount]; 
       bCount++; 
      } else if (var_a[aCount] == var_b[bCount]) { 
       var_c[cCount] = var_a[aCount]; 
       aCount++; 
       cCount++; 
       var_c[cCount] = var_b[bCount]; 
       bCount++; 
      } 
     } 
     for (int i : var_c) { 
      System.out.print(i + " "); 
     } 
    } 
} 

Answer 1

一個共同的解決方案這個問題有三個更換一個循環：

• 第一循環合併兩個陣列，直到其中一個用完的元素
• 山高第二環路轉儲陣列A的其餘元件，如果有的話，到輸出陣列
• 第三循環轉儲陣列B的其餘元件，如果有的話，到輸出陣列

此結構允許用戶使合併循環很簡單：

while (aCount != var_a.length() && b.Count != var_b.length()) { 
    ... // merge 
} 
while (aCount != var_a.length()) { 
    var_c[cCount++] = var_a[aCount++]; 
} 
while (bCount != var_b.length()) { 
    var_c[cCount++] = var_b[bCount++]; 
} 

請注意，最後兩個循環中最多一個將被執行。還要注意使用length()方法來確定數組的長度。這比設置a_size，b_size等更可靠。

Answer 2

相反遍歷合併數組的索引，你可以在單獨的陣列的指標迭代，以確保你永遠不會超出範圍：

int aCount = 0; 
int bCount = 0; 
int cCount = 0; 
while (aCount < var_a.length && bCount < var_b.length) { 
    if (var_a[aCount] <= var_b[bCount]) { 
     var_c[cCount++] = var_a[aCount++]; 
    } else { 
     var_c[cCount++] = var_b[bCount++]; 
    } 
} 
// now add what remains of var_a or var_b 
while (aCount < var_a.length) 
    var_c[cCount++] = var_a[aCount++]; 
while (bCount < var_b.length) 
    var_c[cCount++] = var_b[bCount++]; 

Answer 3

此代碼應遵循的

1. 初始化計數器爲0對於所有3 a_counter，b_counter一個簡單的邏輯，C_C現在
2. 而直到a_c或b_counter小於a_size和分別B_SIZE
   • 將[a_counter]與b [b_counter]進行比較並在c [c_counter]處添加較小的c到c [c_counter]
   • 遞增c_counter，以及哪一個選擇了以上
   • 重複
3. 一旦退出循環，一個的a或b超過
   • 不斷加入到c的所有其餘元素，如果b爲結束;或b如果a已經結束 我相信你不需要代碼，只需改進邏輯;所以沒有給出代碼。

Answer 4

這可能是你想要什麼：

void doArrayThing(){ 
    //the two arrays containing the elements 
    int[] array1 = {1, 3, 5, 2, 7, 5}; 
    int[] array2 = {3, 6, 2, 8}; 

    //the length of the 2 arrays 
    int arrayLength1 = array1.length; 
    int arrayLength2 = array2.length; 

    //the length of both the arrays 
    int containerArrayLength = arrayLength1 + arrayLength2; 

    //the array that holds all the elements 
    int[] container = new int[containerArrayLength]; 

    //a for loop that adds the first array elements 
    for(int i = 0; i < arrayLength1; i++){ 
     //add the elements of the first array 
     container[i] = array1[i]; 
    } 

    //the for loop that adds the second array elements 
    for(int i = 0; i < arrayLength2; i++){ 
     //add the second array elements on top of the first 
     container[i + arrayLength1] = array2[i]; 
    } 

    for(int i = 0; i < containerArrayLength; i++){ 
     //print all the elements 
     System.out.println(container[i]); 
    } 
} 

作用：

它遍歷第一陣列和第二陣列上數字相加，然後遍歷並增加第一個數組元素頂部的元素。

Answer 5

您的算法看起來基本正確。如果沒有通過確切的代碼，我認爲你的問題主要是你有太多的平等，即幾乎你所有的比較是等價的，更少的，更重要的。

如果a == b，那麼也是< = b和a> = b。太多的if語句因此而匹配。密切關注具體的指標應該是什麼，並將您的案例限制在他們應該做的事情上。

我已經重寫了您的代碼（沒有編輯器，對不起，所以它可能無法工作），這應該給你一個很好的主意。

public class Two 
{ 
    public static void main(String[] args) 
    { 
     //sample problem 
     int[] arrayA = {2,3,5,5,8,10,11,17,18,20}; 
     int[] arrayB = {5,6,7,8,14,15,17}; 
     final int sizeA = arrayA.length(); 
     final int sizeB = arrayB.length(); 
     final int sizeC = sizeA+sizeB; 
     int[] arrayC = new int[sizeC]; 
     int countA = 0; 
     int countB = 0; 
     int countC = 0; 
     for (countC = 0; countC < sizeC; countC++) 
     { 
      // if a has run out, fill with b 
      if (countA == sizeA && countB < sizeB) 
      { 
       arrayC[countC] = arrayB[countB]; 
       countB++; 
      } 
      // if b has run out, fill with a 
      else if (countA < sizeA && countB == sizeB) 
      { 
       arrayC[countC] = arrayA[countA]; 
       countA++; 
      } 
      // countA < sizeA && countB < sizeB because 
      // if countA == sizeA && countB == sizeB then also countC == sizeC 
      // and the for-loop would have stopped. 
      else   
      { 
       // mind, if arrayA[countA] == arrayB[countB] then first 
       // a will be added and on the next pass b will be added 
       if (arrayA[countA] <= arrayB[countB]) 
       { 
        arrayC[countC] = arrayA[countA]; 
        countA++; 
       } 
       else 
       { 
        arrayC[countC] = arrayB[countB]; 
        countB++; 
       } 
      } 
     } 
    } 
}