目录

一、题目

二、分析 

2.1 暴力求解法

2.2  找规律

2.3 追求时间效率，以空间换时间

三、结论 

一、题目

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3

输出: [5,6,7,1,2,3,4]

解释:

向右轮转 1 步: [7,1,2,3,4,5,6]

向右轮转 2 步: [6,7,1,2,3,4,5]

向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2

输出：[3,99,-1,-100]

解释:

向右轮转 1 步: [99,-1,-100,3]

向右轮转 2 步: [3,99,-1,-100]

二、分析 

2.1 暴力求解法

这题是旋转字符串但是它的实质是将前面n-1个数据往后移一位，然后将最后一个数据移到第一个，旋转几次则执行几次这个步骤。为了变量不被覆盖，变量采取从后向前移动，而最后一个数据利用一个空变量temp去拷贝一份，在前面数据移动完成后则拷贝到第一个数据。如下面代码：

void rotate(int* num ,int k , int size)

{

k %= size;//size次一次循环

while (k)

{

int temp = num[size-1];

for (int i = size-1; i > 0; i--)

{

num[i] = num[i - 1];

}

num[0] = temp;

k--;

}

}

int main()

{

int arr[] = { 7,1,2,3,4,5,6 };

int size = sizeof(arr) / sizeof(arr[0]);

int k = 1;

printf("旋转几次数组:");

scanf("%d", &k);

printf("旋转前：");

for (int i = 0; i < size; i++)

{

printf("%d ", arr[i]);

}

rotate(arr, k, size);

printf("\n旋转后为：");

for (int i = 0; i < size; i++)

{

printf("%d ", arr[i]);

}

return 0;

}

2.2  找规律

我们发现暴力求解虽然可以解出此题，但是时间复杂度

，那我们有什么办法去降低时间复杂度呢？我们可以尝试降低它的循环次数，找找看他们有什么规律？

如图，将前面n-k个数字逆置然后将后面n个逆置，然后将他们整体逆置。（红色位将要进行逆置的数）

代码如下：

void Inversion(int* arr, int l, int r)

{

while (l < r)

{

int temp = arr[l];

arr[l] = arr[r];

arr[r] = temp;

l++;

r--;

}

}

void rotate(int* nums, int numsSize, int k) {

k %= numsSize;//不让数组越界，完成一次数组长度的旋转数组不变

Inversion(nums, 0, numsSize - k - 1);

Inversion(nums, numsSize - k, numsSize - 1);

Inversion(nums, 0, numsSize - 1);

}

int main()

{

int arr[] = { 7,1,2,3,4,5,6 };

int size = sizeof(arr) / sizeof(arr[0]);

int k = 1;

printf("旋转几次数组:");

scanf("%d", &k);

printf("旋转前：");

for (int i = 0; i < size; i++)

{

printf("%d ", arr[i]);

}

rotate(arr, size, k);

printf("\n旋转后为：");

for (int i = 0; i < size; i++)

{

printf("%d ", arr[i]);

}

return 0;

}

*这里要注意数组越界访问，我们发现数组完成一次数组长度的旋转，数组不变，所以我们取模于数组长度。 

2.3 追求时间效率，以空间换时间

这里我们不讨论空间复杂度只优化时间复杂度，所以我们可以新开辟一段空间，将后n个旋转的数字先放入我们开辟的空间，然后再将前面的n-k个数字放入空间后面。

如代码：

void rotate(int* nums, int numsSize, int k) {

k %= numsSize;

int* temp = (int*)malloc(sizeof(int) * numsSize);

memcpy(temp, nums + numsSize - k, sizeof(int) * k);

memcpy(temp + k, nums, sizeof(int) * (numsSize - k));

memcpy(nums, temp, sizeof(int) * numsSize);

free(temp);//释放临时空间

temp = NULL;

}

int main()

{

int arr[] = { 7,1,2,3,4,5,6 };

int size = sizeof(arr) / sizeof(arr[0]);

int k = 1;

printf("旋转几次数组:");

scanf("%d", &k);

printf("旋转前：");

for (int i = 0; i < size; i++)

{

printf("%d ", arr[i]);

}

rotate(arr, size, k);

printf("\n旋转后为：");

for (int i = 0; i < size; i++)

{

printf("%d ", arr[i]);

}

return 0;

}

三、结论 

每一道题都有属于自己的空间和时间复杂度，当你写出一段代码的时候去想想还能不能继续去优化它，使它的时间和空间复杂度更小。姜糖在这里就是不断在优化它的时间复杂度，从O(N^2)到最后的O(N)。如果大家还有什么不同的看法可以跟姜糖展开讨论哦。