java - 在非满数组中随机选择一个数组元素

Question

我有一个正在创建arrayList的程序。一种方法是从列表中随机删除一个项目。我还有一个方法，如果添加一定数量的元素，可以调整数组大小，以便为需要时添加更多元素腾出空间。

当调整列表大小时，我收到一个 NullPointerExceptionError 消息，然后该方法尝试删除新调整大小的数组中的一个 null 空格。

在不使用 for 循环并保持恒定时间的情况下，我试图找到一种方法使我的 choice 的 int 值只是非 的数量数组中的 >null 元素。我希望这是有道理的 - 有人可以帮忙吗？

删除方法:

public T remove() {
  if (isEmpty()) {
     return null;
  }
  Random rand = new Random();
  int choice = rand.nextInt(size);
  size--;
  elements[choice] = elements[size];
  elements[size] = null;
  return elements[choice];
} 

Answer 1

这个问题归结为“给定一个散布着 null 元素的数组，如何返回第 n 个非 null 元素？”答案是迭代数组，这不支持您正在寻找的恒定时间约束。

但是等等，在这种情况下数组列表如何工作？!？下面是 java.util.ArrayList 的实现方式:

@Override
public E get(int location) {
    if (0 <= location && location < (lastIndex - firstIndex)) {
        return (E) array[firstIndex + location];
    }
    throw new IndexOutOfBoundsException(Messages.getString("luni.0A",
            location, lastIndex - firstIndex));
}

请注意，没有空检查，Arraylist 始终将其元素维护在连续的 block 中，因此获取速度非常快。因此，在删除元素时必须发生一些魔法，这样就不会有空值散落......

@Override
public E remove(int location) {
    E result;
    int localLastIndex = lastIndex;
    int size = localLastIndex - firstIndex;
    if (0 <= location && location < size) {
        if (location == size - 1) {
            result = (E) array[--localLastIndex];
            array[localLastIndex] = null;
        } else if (location == 0) {
            result = (E) array[firstIndex];
            array[firstIndex++] = null;
        } else {
            int elementIndex = firstIndex + location;
            result = (E) array[elementIndex];
            if (location < size / 2) {
                System.arraycopy(array, firstIndex, array, firstIndex + 1,
                        location);
                array[firstIndex++] = null;
            } else {
                System.arraycopy(array, elementIndex + 1, array,
                        elementIndex, size - location - 1);
                array[--localLastIndex] = null;
            }
        }
        if (firstIndex == localLastIndex) {
            firstIndex = localLastIndex = 0;
        }
    } else {
        throw new IndexOutOfBoundsException(Messages.getString("luni.0A",
                location, localLastIndex - firstIndex));
    }
    lastIndex = localLastIndex;
    modCount++;
    return result;
}

key 来了!当删除一个元素时，JDK impl 不会留下间隙，也不会移动所有元素来缩小间隙。它调用一个 native 方法，将数组 block 作为原子操作复制: https://docs.oracle.com/javase/7/docs/api/java/lang/System.html#arraycopy(java.lang.Object,%20int,%20java.lang.Object,%20int,%20int)