你的位置:首页 > Java教程

[Java教程]数组元素循环右移问题

问题:

一个数组A中存有N(N>0)个数, 在不允许使用任何另外数组的前提下, 将每个整数循环右移M(M>0)位, 考虑移动数据的次数尽量少, 要如何设计移动方法?

并分析时间复杂度.

示意图如下:

分析1

当然, 最简单的方法莫过于直接每次向右移动一个, 要移动M位, 就移动M次. 代码如下:

 

//传入操作数组和移动的位数 void moveRight(int Arr[], int M){  //保存下数组的最后一个数   int endNum = Arr[N-1];  //将0~N-2位数向后移动一位  int i;  for(i=N-1; i>0; i--){    Arr[i] = Arr[i-1];  }  //将最后一位数放在第一位  Arr[0] = endNum; }

 

时间复杂度:

每移动一位就需要做N次赋值操作, 如果移动M位,则需要做NM次赋值操作

 

 

分析2

 

我们先将数组分成两部分, 设后面M位为数组b, 前面N-M位为数组a, 那么怎么数组的组成就是ab.

原始数组是ab, 我的目的是将这个数组变成ba

第一步:将整个长度为N的数组倒置得到 b-1a-1 .  

第二步:将 b-1 数组和 a-1 数组分别倒置, 得到 ba数组.

ab  -(倒置整个长度为N的数组)->  b-1a-1  -(分别倒置两个数组)->  ba

//该函数实现将两个变量互换 void Swap(int *a, int *b){  //得到中间变量   *a = *a ^ *b;  //b变量获取到a的值   *b = *b ^ *a;  //a变量通过中间变量获取到当时b的值  *a = *a ^ *b; }

void moveRight(int Arr[], int N, int M){  int i, j;  //转置所有的元素   for(i=N-1, j=0; j<i; i--, j++)    Swap(&Arr[i], &Arr[j]);   //转置前面M个数据  for(i=M-1, j=0; j<i; i--, j++)    Swap(&Arr[i], &Arr[j]);   //转置后面面N-M个数据  for(i=N-1, j=N-M-1; j<i; i--, j++)    Swap(&Arr[i], &Arr[j]); }