[数据结构与算法]leetcode每日一题 189旋转数组

旋转数组问题

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

问题分析：给定数组尚未明确长度、移动k个位置为变量，此时需要考虑情况为k>数组长度是如何旋转，当数组只有一个元素时如何旋转。通过计算发现数组元素下标为i的元素移动后的位置下标为(i+k)%n(n代表原来数组长度），但还未考虑仅有一个元素情况，因此在进行循环时，可采用++i的方法，倘若只有一个数据，则依旧可得出相等的结果。具体代码以及注释如下，（采用辅助空间O(n))
代码：

void rotate(int* nums, int numsSize, int k) {
    int a[numsSize];//新数组存储移动k个位置后元素
    for (int i = 0; i < numsSize; ++i) {//++i先增再计算，避免k>numsSize的情况
        a[(i + k) % numsSize] = nums[i];//每一个nums[i]的值赋值到新的数组中位置为(i+k)%numsSize
    }//这个循环是关键点
    for (int i = 0; i < numsSize; ++i) {
        nums[i] = a[i];//将移动后的数组赋值回来
    }
}

复杂度分析：
时间复杂度：观察for循环运行了n次，因此时间复杂度为O(n)。
空间复杂度：建立了一个长度为n的辅助数组，空间复杂度为O(n)。