首页 > 编程语言 > 详细

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

时间:2017-04-15 14:41:27      阅读:334      评论:0      收藏:0      [点我收藏+]
试设计一个算法,将数组A中的元素A[0]至A[n-1]循环右移k位,并要求只用一个元素大小的附加存储,元素移动或交换次数为O(n).
分析:我们看这个数组123456,循环右移2位。先将数组逆序,654321,交换3次,然后交换前两个,564321,然后右面四个数字逆序,则561234,交换2次,正好是6次,并且在交换数据的时候,只使用了一个附加存储空间,正好满足题意。
void Rotate(char* a,int len)
{  
   int i;
   char temp;
   for(i=0;i<(len+1)/2;i++)
   {
      temp = *(a+i);
      *(a+i) = *(a+len-i);
      *(a+len-i) = temp;
      
   }   
}
 
int main(int argc, char *argv[])
{
  int k;
  printf("Please input number:");
  scanf("%d",&k);
  char a[6] = {‘a‘,‘b‘,‘c‘,‘d‘,‘e‘,‘f‘};
  int i;
  k = k%6;
  Rotate(a,6);
  Rotate(a,k);
  Rotate(a+k,6-k);
  for(i=0;i<6;i++)
  printf("%c",*(a+i)); 
  system("PAUSE");
  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; 
}
 
via:http://blog.sina.com.cn/s/blog_9e62a28b0101jqcv.html
 

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

原文:http://www.cnblogs.com/luckyraye/p/6714179.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!