您当前的位置: 问题:
一个数组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]); }