合併排序索引越界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);