删除项目后删除数组中的"hole"

Question

如果满足条件，我需要从数组中删除一些对象。

从数组中删除对象后，我需要数组没有"洞"，这意味着我需要缩小数组：不是数组大小，而是减少它包含的对象数量。

删除对象后，如果数组末尾有空值，也没关系。

哪种效率更高？

1. 将阵列复制到新阵列中
2. 在数组上迭代，并将元素移动到通过移除对象创建的"孔"上

我必须使用数组，不能使用List实现。

Answer 1

使用ArrayList，这将允许您动态更改结构的大小。

Answer 2

如果您不想使用ArrayList，您可以使用解决方案。但是，与其复制数组，不如创建一个与数组大小相同的空数组，然后将其填充到for循环中。

Answer 3

1）您可以用最后一个元素交换已删除的元素，并制作类似size-- 的东西

2） 如果不能交换，就必须多次使用System.arraycopy(...)方法将数组的一部分复制到新数组中。

public static Object[] deleteElement(Object[] oldArray, int position) {
    Object[] newArray = new Object[oldArray.length - 1];
    System.arraycopy(oldArray, 0, newArray, 0, position);
    System.arraycopy(oldArray, position + 1, newArray, position, newArray.length - position);
    return newArray;
}

Answer 4

根据您的需求，

我需要我的阵列没有任何"洞"，所以我需要"缩小"阵列，

必须创建一个新数组，并将剩余对象移到其中。数组是一个固定大小的构造。不能"收缩"数组。您只能分配新内存并将元素移动到新数组中。

编辑：您应该更改您的问题，以便在数组末尾包含有关允许null的信息。在这种情况下，将元素移回1个索引会更好，因为它消除了内存分配（这是昂贵的），并且将具有平均n/2个操作（假设随机移除），而不是n。

Answer 5

除了第一个需要另一个O（N）内存空间外，您的两个解决方案都是O（N）复杂性的。因此，如果您真的需要处理Array，第二个会稍微好一点。

如果您正在处理一个需要在中间频繁添加和移除的元素数组，我建议您使用Linked-List实现，这样它可以为您提供恒定的时间来添加和移除数组中的任何元素。

Answer 6

下面是一个使用System.arraycopy:的简单示例

    Integer[] i1 = new Integer[] {1, 2, 3, 4, 5};
    Integer[] i2 = new Integer[4];
    // Copy everything, except the third value of i1:
    System.arraycopy(i1, 0, i2, 0, 2);
    System.arraycopy(i1, 3, i2, 2, 2);
    for (int j : i2)
    {
        System.out.println(j);
    }

Answer 7

一些伪代码

• 步骤1：从数组中查找与您希望匹配的对象相匹配的所有对象，并用唯一值覆盖它们（例如：如果您的数组仅包含整数0或更高，则用-1覆盖要删除的对象）
• 步骤1.5：保留一个计数器，记录您删除的金额
• 步骤2：创建一个大小为（oldarray.size-counterFromStep1.5）的新数组
• 步骤3：对于旧数组中的每个非空元素the IS NOT（移除整数），将其添加到新数组中