[数据结构与算法]【力扣】——轮转数组

题目描述：给定一个非负整数k，输出数组nums右移k位后的结果

示例如下：

思路1：

以上图数组为例，假设k=1，前面的元素右移另nums[end]=nums[end-1]即可，在这个过程中nums[end]位置的原数据会被覆盖，且数组的首元素的值也不对，结果如图：

?

所以需要另外一个变量记录nums[end]的原数据，最后赋值给nums[0]

右移k次就是重复上述操作k次

代码如下：

void rotate(int* nums, int numsSize, int k){
    while(k--)
    {
        int tmp=nums[numsSize-1];
        int end=0;
        for(end=numsSize-2;end>=0;--end)
        {
            nums[end+1]=nums[end];
        }
        nums[0]=tmp;
    }

}

?这个方法理论可行，但实际上运行效率特别低

思路2：

1.首先将数组后k个元素进行逆序

2.再将数组剩下的前n-k个元素进行逆序?

3.最后整体进行逆序得到结果

还是图中数组为例

后3个元素逆序后的数组：[1,2,3,4,7,6,5]

前4个元素逆序后的数组：[4,3,2,1,7,6,5]

整体逆序后的数组：[5,6,7,1,2,3,4]

代码如下：

void reverse(int*nums,int left,int right)  //逆序所用的函数
{
    while(left<right)
    {
        int i=nums[left];
        nums[left]=nums[right];
        nums[right]=i;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k){
    if(k>numsSize)
    {
        k=k%numsSize;
    }
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-k-1);
    reverse(nums,0,numsSize-1);
}

结果如图：

此方法同样使用于数组左移的情况，将后k个元素改为前k个元素，前n-k个元素改为后n-k个元素即可

完

?