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

C++语言 码拜 10年前 (2015-05-11) 1391次浏览 0个评论

#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;
}

我在VS2010输出是 2 1 啊,可是提交后说输出是 1 2

#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;
}
10分
参考
http://blog.csdn.net/fightforprogrammer/article/details/44038603
10分
我的代码,时间复杂度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;
            }
    }
}
20分
问题在于Rotate是循环,k=3应该相当于数组的元素在一个大小为2的环形数组中右移三格,也就是转了一圈半,即应为k=1,而你的代码中

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

应改为

k%=numsSize;
恩,谢啦,我代码还是写的有点少

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明Leetcode189题,本地输出与提交输出不一样啊.
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!