[数据结构与算法]Leetcode189. 轮转数组

Every day a leetcode

题目来源：189. 轮转数组

解法1：模拟

每次右移一个，执行k次。

代码：

void oneRotate(int* nums, int numsSize)
{
    int temp=nums[numsSize-1];
    for(int i=numsSize-1;i>0;i--)
    {
        nums[i]=nums[i-1];
    }
    nums[0]=temp;
}
void rotate(int* nums, int numsSize, int k){
    for(int i=0;i<k;i++)
    {
        oneRotate(nums,numsSize);
    }
}

结果：

解法2：辅助数组

我们可以使用额外的数组 temp 来将每个元素放至正确的位置，再拷贝回原数组。

代码：

void rotate(int* nums, int numsSize, int k){
    int *temp;
    temp=(int*)malloc(numsSize*sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        temp[(i+k)%numsSize]=nums[i];
    }
    for(int i=0;i<numsSize;i++)
    {
        nums[i]=temp[i];
    }
}

结果：

解法3：数组反转

代码：

void swap(int* a, int* b){
    int temp=*a;
    *a=*b;
    *b=temp;
}

void reverse(int* nums, int start, int end){
    while(start<end)
    {
        swap(&nums[start],&nums[end]);
        start++;
        end--;
    }
}

void rotate(int* nums, int numsSize, int k){
    k%=numsSize;
    reverse(nums,0,numsSize-1);
    reverse(nums,0,k-1);
    reverse(nums,k,numsSize-1);
}

结果：