可以用翻转法进行数组元素移动。
具体方法如下:
首先对整个数组进行翻转,变成 reversed_array 数组;
将 reversed_array 数组中从下标 0 到下标 k-1 处的元素翻转,变成 reversed_head 数组;
将 reversed_array 数组中从下标 k 到下标 n-1 处的元素翻转,变成 reversed_tail 数组;
将 reversed_head 数组和 reversed_tail 数组重新连接起来,即得到移位后的数组。
代码如下:
void reverse(int* array, int start, int end)
{
while (start < end)
{
std::swap(array[start], array[end]);
++start;
--end;
}
}
void rotateArray(int* array, int n, int k)
{
if (k >= n)
return;
reverse(array, 0, n - 1); // 将整个数组翻转
reverse(array, 0, k - 1); // 将翻转后的数组中前k个元素再次翻转
reverse(array, k, n - 1); // 将翻转后的数组中剩余的元素再次翻转
}
其中,reverse() 函数用于对指定范围的数组元素进行翻转操作,即将从下标 start 到下标 end 的元素进行翻转。rotateArray() 函数接受一个数组、数组长度 n 和要向后移动的位置 k,首先将整个数组翻转,然后将翻转后的数组中前 k 个元素与剩余的元素各自翻转一遍,最后重新连接起来即可得到移位后的数组。
这个算法的时间复杂度为 O(n),并且空间复杂度为 O(1)。
Regenerate response