网站建设app,徐州建筑工程招投标网站,北京橙乐视觉广告有限公司,章丘做网站元素逆置
概述#xff1a;其实就是将 第一个元素和最后一个元素交换#xff0c;第二个元素和倒数第二个元素交换#xff0c;依次到中间位置。用途#xff1a;可用于数组的移动#xff0c;字符串反转#xff0c;链表反转操作#xff0c;栈和队列反转等操作。
逆置图解 …元素逆置
概述其实就是将 第一个元素和最后一个元素交换第二个元素和倒数第二个元素交换依次到中间位置。用途可用于数组的移动字符串反转链表反转操作栈和队列反转等操作。
逆置图解 代码
// 逆置元素算法
void Reverse(int R[] , int l , int r){// R 数组l 左边 r 右边int i , j ,temp;for(il , jr; i j; i,j--){ // i j 不过数组个数是奇数还是偶数都行temp R[i];R[i] R[j];R[j] temp;}
}注意逆置算法很简单但是能延申其他的算法 循环移动算法
考研常考的一个算法结合逆置算法可进行实现
循环左移(右移)算法
图解 第一步循环左移 p 个元素就将 数组前 p 个0~p-1元素先进行逆置第二步再将 数组 p-1位置 之后的n-p个元素进行逆置第三步将 整个数组 整体进行逆置即可得到 循环左移 p 个元素
代码
// 逆置元素算法
void Reverse(int R[] , int l , int r){// R 数组l 左边 r 右边int i , j ,temp;for(il , jr; i j; i,j--){temp R[i];R[i] R[j];R[j] temp;}
}
// 循环左移算法
void LeftMove(int R[] , int n , int p){// r 数组 n 数组元素个数 p 循环左移个数if(p0 || pn){cout ERRORendl; }else{Reverse(r , 0 , p-1); // 先逆置前p个Reverse(r , p , n-1); // 再逆置后n-p个Reverse(r , 0 , n-1); // 最后再把所有的都逆置}
}时间复杂度分析
①第一行 Reverse 执行频度为1 (p-1-01)/2
②第二行 Reverse 执行频度为1 (n-1-p1)/2
③第三行 Reverse 执行频度为1 (n-1-01)/2
f(n) 3 n
T(n) O(f(n)) O(n)空间复杂度
由于可以看到在 整个算法中我们只定义了变量并未定义其他数据结构也未使用递归所以空间复杂度是常数级别。为 O(1)
