织梦网站换空间,淮安建筑信息平台,html5网站推广,seo兼职1. 简述 设计一个算法#xff0c;把一个含有N个元素的数组循环右移K位#xff0c;要求时间复杂度为O(N)#xff0c;且只允许使用两个附加变量。 2. 思路 其实看到题目中只允许两个附加变量应该也能想到#xff0c;就是两个变量倒来倒去就行了。如果熟悉希尔排序的话#x…1. 简述 设计一个算法把一个含有N个元素的数组循环右移K位要求时间复杂度为O(N)且只允许使用两个附加变量。 2. 思路 其实看到题目中只允许两个附加变量应该也能想到就是两个变量倒来倒去就行了。如果熟悉希尔排序的话这题不是问题希尔排序里面需要分组进行插入法排序这里就是分组进行移位而已。 举例先说明下假设10个元素要移动3位那么就是三组第一组A[0],A[3],A[6],A[9]第二组A[1],A[4],A[7]第三组A[2],A[5],A[8]每组分别内部移位即可。 不过有一个问题必须注意假设移动k为数组长度为N当kN/2时没问题但是当kN/2是就不对了当KN/2时每个组都至少有两个元素每个元素都会移动一次而且都是向着应该移动的方向移动指定的位数没有问题。但是当KN/2时有的组会没有元素这样的组不会移动导致错误出现了。解决方法很简单写两个移位函数一个左移一个右移比如N10K7要求左移可以改为N10K3。进行右移即可。 3. 代码 #include iostreamusing namespace std;void left_shift_k(char *a, int n, int k);void right_shift_k(char *a, int n, int k);void left_shift_k(char *a, int n, int k) { k k % n;if(k n/2) { right_shift_k(a, n, n-k);return; }int i,j;char tmp;for(i0; ik; i) { tmp a[i];for(ji; jkn; jk) a[j] a[jk]; a[j] tmp; }}void right_shift_k(char *a, int n, int k) { k k % n;if(k n/2) { left_shift_k(a, n, n-k);return; }int i,j;char tmp;for(i0; ik; i) {for(ji; jkn; jk) ; tmp a[j];for(; ji; j-k) a[j] a[j-k]; a[i] tmp; }}void output(const char* a) {for(int i0; i8; i) cout a[i] ; cout endl;}int main() {char a[8] {a, b, c, d, 1, 2, 3, 4}; cout 数组: endl; output(a);for(int i1; i8; i) {char b[8] {a, b, c, d, 1, 2, 3, 4}; cout 右移 i 位\t; right_shift_k(b, 8, i); output(b); } cout endl; for(int i1; i8; i) {char b[8] {a, b, c, d, 1, 2, 3, 4}; cout 左移 i 位\t; left_shift_k(b, 8, i); output(b); } system(PAUSE);return 0;} 输出结果为 4. 参考 编程之美2.17节数组循环移位转载于:https://www.cnblogs.com/pangxiaodong/archive/2011/10/08/2201766.html
