圆形阵列旋转的线性复杂性实现是否正确?算法 - 圆形阵列旋转
N =元素数目 K =转
int write_to = 0;
int copy_current = 0;
int copy_final = a[0];
int rotation = k;
int position = 0;
for (int i = 0; i < n; i++) {
write_to = (position + rotation) % n;
copy_current = a[write_to];
a[write_to] = copy_final;
position = write_to;
copy_final = copy_current;
}
好,复杂度是线性的肯定。但是如果你希望通过'#rotation'位置来旋转数组中的值,传统上将其描述为循环旋转,当这不是最终结果时,你会感到惊讶。 –
http://stackoverflow.com/questions/11893053/circular-left-shift-of-an-array-by-n-positions-in-java – vadim
@vadim:对这个问题的接受答案肯定是正确的,但更漂亮解决方法是:1.反转第k个元素。 2.反转其余的元素。 3.反转整个阵列。 (所有反转都在原地。) – rici