对于从一个圆圈中的arraylist中删除每个第K个元素的问题,提供了答案:
import java.util.ArrayList;
public class MyClass {
public static void main(String[] args) {
ArrayList <Integer> list1 = new ArrayList();
int n = 10;
int k = 3;
for (int i = 0; i<n; i++){
list1.add(i+1);
}
int pos =0;
while (list1.size()!=1)
{
pos = (pos+k-1)%list1.size();
list1.remove(pos);
}
System.out.print(list1.get(0));
}
}
这是一个二次O(n²)算法,但它似乎并不明显,因为它会导致问题:
...您在哪里看到 n^2 ?...有一个while循环,每次迭代“删除”一个元素,这里的正方形在哪里?
流行的 Java 实现如何表现?语言规范是否保证任意索引的O(n)行为?ArrayList.remove(i)
来自关于ArrayList的 Java API 规范:
size
,isEmpty
,get
,set
和是在恒定时间内执行的iterator
。listIterator
该操作需要O(1)add
摊销时间,这意味着将在O(n)中添加n 个元素。所有其他操作都在线性时间内执行(粗略地说)。ArrayList.remove()
属于“其他操作”类别,因此删除一个任意元素是O(n)操作。循环从问题中一个一个地删除项目(总共n次删除)。总计:n * O(n) = O(n * n)即问题中提出的算法是二次的。好问题,我会解释这里发生了什么。关键是集合实现
ArrayList
是基于数组的。如您所知,内存是以块为单位分配给数组的,因此对元素的访问是在恒定时间内进行的 - 只需通过其索引即可。如果不是为了一个 BUT,也有可能到此结束。当一个元素被移除时,数组中被移除元素的索引之后的所有元素
ArrayList
都向左移动一个位置。现在让我用一个例子来解释。源数组:我们这样做
.remove(3)
并得到这个状态:之后,数组的最后一个索引(最后一个数字 6)设置为零。
转移是使用原生方法进行的
System.arrayCopy()
,该方法不是用 Java 编写的,并且比通常的手动逐个元素复制快很多倍,但是,它的大 O 表示法的速度估计接近 O(n) .对于
LinkedList
基于双向链表的 c 的情况,即使我们按索引删除,我们仍然需要在删除之前找到该元素,这是一个正常的 O(n) 线性搜索。