我幾乎正確地實作了整個 Bag 類，并且它已被證明可以作業，除了這個 remove 方法。整體時間復雜度應該是 O(length)。我試圖通過將要洗掉的元素移動到陣列的末尾并將其與最后一個元素交換來完成此操作。然后，我使用 Arrays.copyOf() 截斷陣列。
public void remove(String s)
{
for (int i = 0; i < length; i ) {
if(bag[i].equals(s)){
// Adding bag[i] to end of array:
if (length == SIZE){
SIZE *= 2;
bag = Arrays.copyOf(bag, SIZE);
}
bag[length] = bag[i];
// Moving last element to bag[i]:
bag[i] = bag[length-1];
bag = Arrays.copyOf(bag, length-1);
length--;
}
}
}
如果您查看我的輸出，則洗掉成功并洗掉了“Cucumber”，但是當我洗掉串列中的第一個元素“Cabbage”時，會導致索引越界錯誤。
輸出：
ADD Guava
Bag: {Cabbage, Cucumber, Broccoli, Banana, Broccoli, Guava}
REMOVE Cucumber
Bag: {Cabbage, Guava, Broccoli, Banana, Broccoli}
REMOVE Cucumber
Bag: {Cabbage, Guava, Broccoli, Banana, Broccoli}
REMOVE Cabbage
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
at ArrayBag.remove(ArrayBag.java:84)
at Main.<init>(Main.java:53)
at Main.main(Main.java:15)
Process finished with exit code 1
我非常感謝任何幫助我理解為什么會出現這個錯誤。謝謝！
uj5u.com熱心網友回復：
袋子是事物的無序集合。洗掉包中專案的最快方法是將其替換為陣列中的最后一項并減少計數。以下是洗掉專案的方法。我洗掉了void add(String item)andString toString()方法，只顯示了 remove 方法。O(n) 因為對陣列中的專案進行線性搜索。
class Bag {
private String[] items = new String[100];
private int size = 0;
void remove(String item){
int index = indexOf(item);
if (index >= 0)
items[index] = items[--size];
}
private int indexOf(String item){
for(int i=0; i<size; i )
if (items[i].equals(item))
return i;
return -1;
}
}
示例用法：
public class Main{
public static void main(String[] args) {
Bag b = new Bag();
b.add("apple");
b.add("banana");
b.add("orange");
System.out.println(b);
b.remove("banana");
System.out.println(b);
b.remove("apple");
System.out.println(b);
}
}
輸出
Bag [apple, banana, orange]
Bag [apple, orange]
Bag [orange]
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/424745.html