仅使用Java数组实现Bag

Question

我几乎已经正确地实现了整个Bag类，并且已经证明它可以工作，除了这个remove方法。总体时间复杂度应为O(长度(。我试图通过将要移除的元素移动到数组的末尾并将其与最后一个元素交换来实现这一点。然后，我使用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"是成功的，但当我删除列表中的第一个元素"卷心菜"时，会导致索引越界错误。

输出：

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

如果您能帮助我理解为什么会出现这个错误，我将不胜感激。非常感谢。

Answer 1

袋子是一组无序的东西。移除袋子中物品的最快方法是将其替换为数组中的最后一个物品并递减计数。以下是删除项目的方法。我删除了void add(String item)和String 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]