把一个含有N个元素的数组循环右移K位，要求时间复杂度为O(N)

分析与解法

假设原数组序列为abcd1234，要求变换成的数组序列为1234abcd，即循环右移了4位，比较之后，不难看出，其中有两段的顺序是不变的：1234和abcd，可把两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换过程通过以下步骤完成：

1.逆序排列 abcd: abcd1234 -> dcba1234;

2.逆序排列 1234: dcba1234-> dcba4321;

3.全部逆序 dcba4321->1234abcd。

C# Codes

using System;


namespace ConsoleApp2
{
class Program
{
static void Main(string[] args)
{
int[] array ={ 1, 2, 3, 4, 5, 6, 7, 8, 9};
RightShift(array, 5);


foreach (int i in array)
{
Console.WriteLine(i);
}


Console.ReadKey();
}


static void Reserve(int[] array, int startIndex, int endIndex)
{
for (int i = 0; i < (endIndex - startIndex + 1) / 2; i++)
{
int mark = array[startIndex + i];
array[startIndex + i] = array[endIndex - i];
array[endIndex - i] = mark;
}
}


static void RightShift(int[] array, int shiftNum)
{
shiftNum %= array.Length;


if (shiftNum <= 0)
{
return;
}


Reserve(array, 0, shiftNum - 1);
Reserve(array, shiftNum, array.Length - 1);
Reserve(array, 0, array.Length - 1);
}
}
}