合并排序索引越界java
嘿,我正在合并排序方法,不断收到一个索引越界的错误。我无法弄清楚为什么或在哪里发生。我试过打印索引并查看递归中是否有错误,但我认为它不是非常简单的。合并排序索引越界java
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;
}
你的问题是,像这样的台词:
temp.set(total,words.get(first1));
你在一个ArrayList
已经在没有元素这样做。当你调用.set()
时,你必须传递一个已经在数组中的元素的索引(即total<temp.size()
)。
我想你想要两个临时列表,并且您想要使用ArrayList.add()
而不是ArrayList.set()
将左半部分的内容放入第一个,将右半部分放入第二个列表。然后你可以将它们合并回原来的ArrayList
(在这里,你真的可以使用words.set()
,因为它已经有了元素,只是顺序错误)。
我改变了设置添加,我仍然越界,但现在它已经退出第一个while循环之后它的第61行。 – user3400512 2014-09-30 16:11:03
@ user3400512是的,我已经指出了为什么你会在该行发现错误,但是你需要重新编写代码以获得完整的解决方案。正如我所说的,你需要两个临时列表,一个用于数组的每一半,这样你就可以将它们合并回来。 – 2014-09-30 17:11:06
您的问题是您在空的临时列表上使用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);
我实现了循环,并且我仍然在同一个地方得到索引超出绑定异常 – user3400512 2014-09-30 16:36:00
我看到您已编辑程序以通过添加(索引,对象)替换set(index,object)。但是,您使用add()的错误版本。您需要使用添加(对象)添加到列表末尾,而不是作为不存在的特定索引,因为您从空的临时列表开始 – 2014-09-30 19:38:56
而且您还可以删除“总计”变量。这不是全部需要的 – 2014-09-30 19:39:29
为什么不你看看例外吗?它告诉你在哪里... – Alboz 2014-09-30 16:01:47
请标记一条线,发生错误 – talex 2014-09-30 16:01:50
它告诉我线50 – user3400512 2014-09-30 16:04:52