LeetCode 189.轮转数组 C写法 三段逆置
思路:
三段逆置方法:先逆置前n-k个 再逆置后k个 最后整体逆置
由示例1得，需要先逆置1,2,3,4 再逆置5,6,7，最后前n-k个与后k个逆置
代码
void reverse(int*num, int left, int right) //逆置函数
{
while(left < right) //left和right同时移动，相遇则逆置完成
{
int tmp = num[left];
num[left] = num[right];
num[right] = tmp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k) {
if(k > numsSize) //当k大于numsSize时就说明轮转完了一轮，则数组不变
k %= numsSize; //余数为新一轮的轮转数
reverse(nums, 0, numsSize - k - 1); //从0开始，则n-k的位置实际为n-k-1
reverse(nums, numsSize - k, numsSize - 1); //从n-k开始，实际为后k个的位置
reverse(nums, 0, numsSize - 1); //整体逆置
}
时间复杂度O(N) 空间复杂度O(1):
