ArrayList随机索引删除：交换末位实现O(1)时间是否正确？

这种在允许打乱元素顺序的前提下，通过交换目标索引元素与末尾元素，再删除末尾元素的方式，确实能把ArrayList随机索引删除的时间复杂度降到O(1)，具体原因如下：

• ArrayList的底层实现是动态数组，常规删除非末尾元素时，需要将目标索引之后的所有元素向前移位，这一步的时间复杂度是O(n)（n为列表长度）
• 你的方案里的核心操作都是常数时间：
  • 生成范围内的随机索引：属于O(1)操作
  • 交换目标索引与末尾元素：数组通过下标直接访问元素，交换仅需两次赋值，是O(1)
  • 删除末尾元素：只需修改ArrayList的size标记，无需移动任何元素，同样是O(1)

这种技巧是处理无需保持顺序的集合删除场景时，优化时间复杂度的常用手段，完全符合你的需求。

内容的提问来源于stack exchange，提问作者spectrbro