基于java算法的数组滑动

Question

我正在用java编写一个程序,我需要滑动数组的元素,它应该尽可能少地执行操作,因为它在双循环中并且我正在处理数组的长度,范围从10到10 ^ 8.

示例:A = {1,2,3,4,5,6}结果:第一次A = {2,3,4,5,6,1} A = {3,4,5,6,1, 2}第二次等等..

请随意建议任何其他数据结构或对阵列的任何修改!感谢你们!!:d

Answer 1

实现这种效果的最简单方法是做一个"圆形阵列"; 也就是说,您可以简单地存储标记数组开头的索引,而不是移动数组的内容.

要获取索引i处的项目,您可以执行以下操作:

Type item = arr[(offset + i) % arr.length];

这样,您将获得与数组中相同的属性,并且可以在O(1)中执行任何旋转.

为了减少使用麻烦,你可以制作一个简单的包装类,简单地包装一个数组,允许通过这个方法轻松旋转.这样,代码看起来很干净,同时你可以获得有效的轮换.

Answer 2

为了实现O(1)复杂性,你可以......

1. 使用链表
2. 使用存储起始位置的类包装数组,并允许您通过"虚拟"索引访问数组(wrapped.acces(i)=> array [(start + i)%array.length]
3. "加倍"你的数组并以适当的方式对其进行切片(这样你就不必更改周围的代码)

否则,如果你想坚持你的数据结构,你需要支付O(n),无论如何.

我选择(2),因为它对随机访问和线性访问模式都更快(数组具有更好的数据局部性+ O(1)随机访问复杂度和链表的O(n).