在线性时间内旋转数组的算法 [英] Algorithm to rotate an array in linear time

问题描述

如何仅在线性时间内使用 swap 函数将整数数组旋转 i 次.

How to rotate an integer array by i times using swap function only in linear time.

推荐答案

您可以使用 reverse() 助手在线性时间内完成此操作.

You can do this in linear time by using a reverse() helper.

// rotate array of size=size, by n positions
void rotate(int array[], int size, int n)
{
  // reverse array[0...size-1]
  reverse(array, 0, size-1);

  // reverse A[0...n-1]
  reverse(array, 0, n-1);

  // reverse A[n...size-1]
  reverse(array, n, size-1);
}

// reverse elements in the array[pos_from ... pos_to]
void reverse(int array[], int pos_from, int pos_to)
{
   ...
}

使用交换实现reverse(int array[], int pos_from, int pos_to) 留给读者作为练习.提示:这可以在线性时间内完成.

Implementing reverse(int array[], int pos_from, int pos_to) using swaps is left as an exercise for the reader. Hint: This can be done in linear time.

这篇关于在线性时间内旋转数组的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！