合并不等长的排序数组

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++; 
       } 
      } 
     } 
    } 
}