合并排序索引越界java

Question

嘿，我正在合并排序方法，不断收到一个索引越界的错误。我无法弄清楚为什么或在哪里发生。我试过打印索引并查看递归中是否有错误，但我认为它不是非常简单的。

public ArrayList<String> mergeSort(ArrayList<String> words,int first, int last){ 

    if (first < last){ 
     int mid = (first+ last)/2; 
     mergeSort(words,first,mid); 
     mergeSort(words,mid+1,last); 
     merge(words, first, mid, last); 
    } 
    return words; 

} 
public ArrayList<String> merge(ArrayList<String> words, int first, int mid, int last){ 
    int first1 = first; 
    int last1 = mid; 
    int first2 = mid+1; 
    int last2 = last; 
    int total = first1; 
    ArrayList<String> temp = new ArrayList<String>(); 
    while ((first1<=last) && (first2 <= last2)){ 
     if (words.get(first1).compareTo(words.get(first2))<=0){ 
      temp.add(total,words.get(first1)); 
      first1++; 
     } 
     else{ 
      temp.add(total,words.get(first2)); 
      first2++; 
     } 
     total++; 
    } 
     while(first1 <= words.size()){ 
      temp.add(total,words.get(first1));// exception occurs here 
     first1++; 
     total++; 
     } 
     while (first2 <= last2){ 
      temp.add(total,words.get(first2)); 
      first2++; 
      total++; 
     } 
    for (total = first; total <= last; ++total){ 
     words.set(total,temp.get(total)); 
    } 
    System.out.println(words); 
    return words; 
} 

Answer 1

你的问题是，像这样的台词：

temp.set(total,words.get(first1)); 

你在一个ArrayList已经在没有元素这样做。当你调用.set()时，你必须传递一个已经在数组中的元素的索引（即total<temp.size()）。

我想你想要两个临时列表，并且您想要使用ArrayList.add()而不是ArrayList.set()将左半部分的内容放入第一个，将右半部分放入第二个列表。然后你可以将它们合并回原来的ArrayList（在这里，你真的可以使用words.set()，因为它已经有了元素，只是顺序错误）。

Answer 2

您的问题是您在空的临时列表上使用set()。 set()替换数组中的一个元素，但数组为空：没有要替换的元素。

你需要做的是将add()放入临时列表中，而不是使用set()。这些元素将按顺序添加，因此按照正确的顺序添加，您不需要使用total变量。

现在，当用单词替换元素时，它会有所不同。临时列表将具有从0到(last - first)索引的元素，并且您想用文字替换从first到last的元素。对于这一点，我认为下面的循环将工作：

for (String word : temp) { 
    words.set(first++, word); 
} 

注：因为你事先知道温度（即last - first + 1）的最终大小，你应该使用预先分配的：

ArrayList<String> temp = new ArrayList<String>(last - first + 1);