Leetcode189题,本地输出与提交输出不一样啊.

#include <iostream>
#include<malloc.h>
using namespace std;

void rotate(int* nums, int numsSize, int k)
{
	int j=k-1,m=k-1;
	int *temp =(int *)malloc(k*sizeof(int));
	if (numsSize<k)
	{
		k=numsSize;
	}
	for (int i=numsSize-1;i>=(numsSize-k);i--)
	{
		temp[j]=nums[i]; cout<<temp[j]<<"   ";
		j--;
	}
	cout<<endl;

	for (int i=0;i<numsSize;i++)
	{
		if(i<numsSize-k)
		{
			nums[numsSize-i-1]=nums[numsSize-k-1-i];
		}
		else 
		{
			nums[numsSize-i-1]=temp[m];
			m--;
		}
	}

	for (int i=0;i<numsSize;i++)
	{
		cout<<nums[i]<<"  ";
	}

}
 
int main()
{
	int nums[]={1,2};  
	int numsSize=2,k=3;
	rotate(nums,numsSize,k);
	return 0;
}

参考
http://blog.csdn.net/fightforprogrammer/article/details/44038603

我的代码，时间复杂度O(n),空间复杂度O(1)

void rotate(int* nums, int numsSize, int k) {
    k%=numsSize;
    if(k) {
        int cur,last,i,j,index;
        int gcd=numsSize,b=k;
        while(b) {
            i=gcd;
            gcd=b;
            b=i%b;
        }
        b=numsSize/gcd;
        for(i=0;i<gcd;++i)
            for(j=b,index=i,last=nums[i+numsSize-k];j>0;--j) {
                cur=nums[index];
                nums[index]=last;
                index+=k;
                if(index>=numsSize)index-=numsSize;
                last=cur;
            }
    }
}

问题在于Rotate是循环，k=3应该相当于数组的元素在一个大小为2的环形数组中右移三格，也就是转了一圈半，即应为k=1,而你的代码中

if (numsSize<k)
{
    k=numsSize;
}

应改为

k%=numsSize;

恩，谢啦，我代码还是写的有点少