天津旅游网站建设,辽宁省建设工程信息网官网电话,佛山商城网站建设,文化传媒公司名字大全1、A[n]#xff0c;k#xff0c;将数组向右循环移动k位。要求时间复杂度O(n)#xff0c;空间O(1)。
思路#xff1a;采用三次反转数组的操作#xff0c;可以实现时间复杂度为O(n)#xff0c;空间复杂度为O(1)的算法。
void moveElem(int array[],int k,int length){//a…1、A[n]k将数组向右循环移动k位。要求时间复杂度O(n)空间O(1)。
思路采用三次反转数组的操作可以实现时间复杂度为O(n)空间复杂度为O(1)的算法。
void moveElem(int array[],int k,int length){//array是需要循环移动元素的数组k是需要移动的位数length是数组的长度int temp;//先将整个数组反转for(int i0;ilength/2;i){temparray[length-1-i];array[length-1-i]array[i];array[i]temp;}//再反转前K个元素这样就使得原本在倒数k个位置的元素来到了数组前K个位置相当于后k个元素都前进了k位for(int i0;ik/2;i){temparray[k-1-i];array[k-1-i]array[i];array[i]temp;}//再反转下标为k到n-1的所有元素相当于前n-k个元素后移了k位for(int ik;i(lengthk)/2-1;i){temparray[lengthk-1-i];array[lengthk-1-i]array[i];array[i]temp;}
}
2、给定一个无向无权图G对所有顶点排序按照每个顶点到顶点V的最短路径长度非增排序。要求时间复杂度O(ne) n:顶点数 e:边数
bool visited[MaxVertexNum]; // 访问数组
char distSorted[MaxVertexNum]; // 保存排序信息
int len; // 路径长度或者理解为广度优先搜素层数
void BFSTraverse(ALGraph G, int K, int v) // 邻接表存储图
{for (int i 0; i G.vernum; i){visited[i] false; // 初始化访问数组dist[i] -1; // 初始化最短路径数组}Queue Q;InitQueue(Q); // 初始化队列// 从顶点V开始搜索// 更新访问数组visited[v] true;distSorted[0] G.vertices[v].data;int i0;// 将结点V入队EnQueue(Q, v);while (!IsEmpty(Q)){ // 当队列不空时DeQueue(Q, v); // 队首顶点出队并用V保存该顶点for (ArcNode *p G.vertices[v].firstarc; p; p-nextarc){ // 检测所有V的邻接点int w p-adjvex; // w即为邻接点if (visited[w] false){ // 当前节点未访问// 更新访问数组visited[w] true;distSorted[i] G.vertices[v].data;EnQueue(Q, w); // w入队}}}//给结点排序由于广度优先搜索形成的结点是按照距离由小到大保存的因此只要反转数组即可for(int i0;iG.vernum/2;i){char tempdistSorted[G.vernum-1-i];distSorted[G.vernum-1-i]distSorted[i];distSorted[i]temp;}
}
3、struct BinNode{ int size;//以该结点为根的子树的总结点数 BinNode *left,*right;
}
实现BinNode* rank(BinNode *t,int k)
功能为找到先根序列中第K个结点返回其地址。要求不使用先序遍历且时间复杂度为0depth(x)),depth(x)为结点x的深度。
BinNode *rank(BinNode *t, int k)
{if (!t)return nullptr; // 如果树为空返回空// 如果第k个节点就是当前节点if (k 1)return t;// 如果第k个节点在左子树中if (k t-left-size1){return rank(t-left, k-1);}else{// 如果第k个节点在右子树中return rank(t-right, k - t-left-size - 1);}
}
按照先序遍历的规则根节点是先序遍历中的第1个节点然后先遍历完左子树才会遍历右子树因此如果k小于左子树上节点的个数那么说明第k个节点在其左子树上因此继续往左寻找。而如果k大于左子树上的节点个数就说明k在右子树上因此向右寻找。
