学步园

一、问题描述

定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef左旋转2位得到字符串cdefab。
请实现字符串左旋转的函数，要求对长度为n的字符串操作的时间复杂度为O(n)，空间复杂度为O(1)。

二、算法分析

实现此函数的功能并不复杂，复杂之处在于对函数在时间和空间上提出的要求。看到别人提出了一种很好的算法，能够在时间和空间上满足要求，算法流程图如下：先反转前r个字符，再反转后n-r个字符，最后反转整个数组。这样既实现了功能，又在时空上都满足了限制。

算法流程图

三、代码实现

/*
Description:array_len means the array's length, this function can swap the numbers from array[begin] to array[end]
output:void
此函数实现了反转给定数组array[array_len]中从array[begin]到array[end]中的元素的功能，要求输入满足：0<=begin<=end<array_len 
*/
void swap_array(int array[], int array_len, int begin, int end)
{
    int i = 0;
    int temp = 0;
    int sum = 0;
    int len = 0;
    
    sum = begin + end;
    len = end - begin + 1;
    if(begin < 0 || end >= array_len || begin > end)
    {
        printf("error: wrong value of begin or end !\n");
        exit(1);
    }
    if(begin == end) //only one value, and it's not necessary to change, it's ok
    {
        return ;
    }
    for(i = begin; i < begin + len / 2; i ++)
    {
        temp = array[i];
        array[i] = array[sum -i];
        array[sum -i] = temp;
    }
}

void left_circle_r_position(int array[], int array_len, int r)
{
	if(array_len < 0 || r < 0 || r > array_len)
	{
		printf("wrong parameter !\n");
		exit(1);
	}
	if(r == array_len || r == 0) //it's already ok
	{
		return ;
	}
	swap_array(array, array_len, 0, r-1);
	swap_array(array, array_len, r, array_len);
	swap_array(array, array_len, 0, array_len);
}

void display_array(int array[], int array_len)
{
	int i = 0;
	
	for(i = 0; i < array_len; i ++)
	{
		printf("%3d",array[i]);
	}
	printf("\n");
}