外部排序=读写外存时间+内部排序所需时间+内部归并所需时间优化：1.增加归并路数（内存开销大）（关键字对比次数增加）------败者树（k-1，logk向上取整）2.减少初始归并段数量r------置换选择排序k叉哈夫曼树（最小读写次数）-------设虚段（r-1)%（k-1）=u, 虚段数：k-1-u

时间复杂度o(r)空间复杂度o(d(n+r))稳定

有序序列两两合并稳定空间复杂度O（n）,时间复杂度O(nlogn)int* B = (int*)malloc(sizeof(int) * n);void sort(int num[], int low, int high) { if (low < high) { int mid = (low + high) / 2; sort(num, low, mid); sort(num, mid+1, high); Merge(num, low, mid, high); }}void Merge(int num[],int low,int mid,int high) { int i, j,...

空间复杂度O(1)时间复杂度O(nlogn)插入：从队尾插入删除：由队尾元素代替然后进行heapadjust()；void BuildMaxheap(int num[], int len) { int i = 0; for (i = len / 2;; i--) {//从分支节点开始， HeapAdjust(num,i,len); }}void HeapAdjust(int num[], int k, int len) { num[0] = num[k]; for (int i =k*2 ; i < len; i *= 2) {// if (num[i] < num[i + 1...

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @param p int整型 * @param q int整型 * @return int整型 */ int lowestCommonAncestor(struct TreeNode* root, int p, int q ) ...

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pRoot TreeNode类 * @return bool布尔型 */ int depth(struct TreeNode* pRoot){//求树的度 if(pRoot==NULL){ return 0; } if(...

BM32 合并二叉树题目题解(3)讨论(6)排行面经new简单  通过率：65.89%  时间限制：1秒  空间限制：256M知识点树描述已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：两颗二叉树是:                                                                    Tree 1                                                                        Tree 2        ...

描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示数据范围：输入二叉树的节点数 0≤𝑛≤10000≤n≤1000，二叉树中每个节点的值 0≤𝑣𝑎𝑙≤10000≤val≤1000要求：空间复杂度𝑂(1)O(1)（即在原树上操作），时间复杂度 𝑂(𝑛)O(n)注意:1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继2.返回链表中的第一个节点的指针3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构4.你不用输出双向链表，程序会根据你的返回值自动打印输出输...

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * * @param pRootOfTree TreeNode类 * @return TreeNode类 */ static struct TreeNode* pre =NULL; //中序遍历 void mid(struct TreeNode* p ){ if(!p){ //出口条件，节点为空 return ; } mid(p-&...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param height int整型一维数组 * @param heightLen int height数组长度 * @return int整型 */ int getmin(int a,int b){ return a>=b? b:a; } int getmax(int a,int b){ return a>=b? a:b; } int maxArea(int* height, int heightLen ) { // write code he...

NC37 合并区间题目题解(219)讨论(302)排行面经new中等  通过率：24.90%  时间限制：2秒  空间限制：256M知识点排序数组描述给出一组区间，请合并所有重叠的区间。请保证合并后的区间按区间起点升序排列。数据范围：区间组数 0≤𝑛≤2×1050≤n≤2×105，区间内 的值都满足 0≤𝑣𝑎𝑙≤2×1050≤val≤2×105要求：空间复杂度 𝑂(𝑛)O(n)，时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛)O(nlogn)进阶：空间复杂度 𝑂(𝑣𝑎𝑙)O(val)，时间复杂度𝑂(𝑣𝑎𝑙)O(val)示例1输入： [[10,30],[20,60],[80,...

char c[10000]; int top=0; void push(char a){ printf("%c",a); c[top++]=a; } bool pop(char a){ if(a==']'&& '['==c[top-1]){//判断是否匹配 top--; printf("%d ",top); return true; } if(a==')'&& '('==c[top-1]){//判断是否匹配 top--;...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param node int整型 * @return 无 */ //声明一个全局变量 int n[1000], top = 0; int m[1000], tp=0; void push(int node ) { // write code here //判断pop栈里是否有数据，如果有，则输出到push栈 while(tp) n[top++]=m[--tp]; n[top++]=node; } int pop() { ...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 计算两个数之和 * @param s string字符串 表示第一个整数 * @param t string字符串 表示第二个整数 * @return string字符串 */ char* solve(char* s, char* t ) { // write code here int s1 = strlen(s) - 1; int t1 = strlen(t) - 1; printf("%d %d\n",s1,t1); //...