今晚做了下某公司的网络笔试题,好久没刷题了,现在渣得要死,里面有道程序设计题是 把一个数组向右循环移动k位要求时间复杂度为O(n) 给的方法定义为
public void solution(int a[],int length,int k)
我当时觉得挺容易的,结果一写出来发现只能移一位。。。
public void solution(int []a,int length,int k){ int temp=a[length-1]; for(int j=length-1;j>0;j--){ a[j]=a[j-1]; } a[0]=temp; }
然后发现再加个循环不就可以移动k位了吗?。。可是时间复杂度为O(k*n)了。。最后O(n)的算法有问题没时间了就用了这个。。
public void solution(int []a,int length,int k){ for(int i=0;i<k;i++){ int temp=a[length-1];//这里最后还写错了没减一。。 for(int j=length-1;j>0;j--){ a[j]=a[j-1]; } a[0]=temp; } }
其实这里有个算法:先将前n-k个数逆置,然后将后k个数逆置,最后整个数组逆置。
左移是先将前k个数倒序,然后将后n—k个数倒序
#include<iostream.h> void convert(int a[], int start, int end) { int k, temp; for (k = 0; k < (end-start+1)/2; k++) { temp = a[start+k]; a[start+k] = a[end-k]; a[end-k] = temp; } } void yiwei(int a[], int n, int k) { convert(a,0,n-k-1);//将数组前n-k个数逆置(0~n-k), convert(a,n-k,n-1);//将数组后k个数逆置(n-k~n-1), convert(a,0,n-1);//将整个数组逆置, } void main() { int a[6] = {1,2,3,4,5,6}; yiwei(a,6,2); for (int i = 0; i < 6; i++) cout << a[i] << ' '; }