当前位置: 首页 > >

算法题---数组元素循环右移

发布时间:

试设计一个算法,将数组A中的元素A[0]至A[n-1]循环右移k位,并要求只用一个元素大小的附加存储,元素移动或交换次数为O(n).


分析:我们看这个数组123456,循环右移2位。先将数组逆序,654321,交换3次,然后交换前两个,564321,然后右面四个数字逆序,则561234,交换2次,正好是6次,并且在交换数据的时候,只使用了一个附加存储空间,正好满足题意。




?


#include #include #include #define maxsize 20 int arr[maxsize];


using namespace std;


void exchange_tool(int* arr, int len)


{ ?int i; ?


int temp;


?for (i = 0; i<(len + 1) / 2; i++) ?{ ??temp = *(arr + i); ??*(arr + i) = *(arr + len - i); ??*(arr + len - i) = temp;}


}


void rotate(int*arr, int n, int m)


{ ?m = m%n;


?exchange_tool(arr, n); ?


exchange_tool(arr, m); ?


exchange_tool(arr + m, n - m);


}


int main()


{ ?int n, k, i;


?while (1) ?{ ??


cout << "数组长度?" << endl; ??cin >> n; ?


?cout << "右循环几位?" << endl; ?


?cin >> k;


??cout << "输入数字:" << endl;


??for (i = 0; i < n; i++) ??{ ???cin >> *(&arr[i]);?}


??rotate(arr, n, k); ?


?for (i = 0; i < n-1; i++) {cout << arr[i] << " "; ?}


?cout << arr[i] << endl; ?


?cout << endl;


?} ?


?return 0;


}





其中有2个地方要注意


1.
for(i=0;i<(len+1)/2;i++),正好可以避开奇数和偶数的判断,大家自己琢磨一下。


2.k = k%6;k的次数有可能大于6,,6的整数倍的右移还是本身,于是就求余吧。


其实这道题目一个元素的附加存储空间都可以省去,因为交换两个值不需要附加空间,我们有^.


如下:



void swap(char& a,char& b)


{


? ?a = a^b;


? ?b = a^b;


? ?a = a^b;?


}



这里用到了引用。大家推导一下,因为a^a = 0和a^0 = a。如果用指针的话,如下:



void swap(char* a,char* b)


{


? ?*a = *a^*b;


? ?*b = *a^*b;


? ?*a = *a^*b;?


}


?


?






转载于:https://www.cnblogs.com/luckyraye/p/6714179.html






相关资源:最新Java JDK 8安装版(Windows 64位)



友情链接: