仅使用 Java 数组实现 Bag

Question

我几乎正确地实现了整个 Bag class，并且它已被证明可以工作，除了这个删除方法。整体时间复杂度应该是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

如果能帮助我理解为什么会出现此错误，我将不胜感激。谢谢！

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]

仅使用 Java 数组实现 Bag

Implementation of Bag using only a Java Array

java

arrays

for-loop

copy

indexoutofboundsexception