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):