首页 > 代码库 > 笔试算法题（31）：将有序数组转换成BST表示 & 线段树的应用

笔试算法题（31）：将有序数组转换成BST表示 & 线段树的应用

2024-07-05 22:15:07   222人阅读

出题：要求将一个有序整数数组转换成最小深度的Binary Search Tree表示；

分析：由于需要是最小深度，所以BST应保持平衡，左右节点数大致相当，并且BST中当前根节点大于所有其左子树中的元素，小于所有其右子树中的元素。对于排序数组而言，中间元素必然作为根节点，然后递归对由中间元素分割的左右数组部分进行处理；

解题：

 1 struct Node {
 2         int value;
 3         Node *left;
 4         Node *right;
 5 };
 6 
 7 Node* Array2BST(int *array, int i, int j) {
 8         /**
 9          * 如果上下范围相同说明只有一个节点
10          * 直接返回
11          * */
12         if(i==j) {
13                 Node *root=new Node();
14                 root->value=http://www.mamicode.com/array[i];
15                 root->left=NULL;
16                 root->right=NULL;
17                 return root;
18         }
19 
20         int m=(i+j)/2;
21         Node *root=new Node();
22         root->value=http://www.mamicode.com/array[m];
23         /**
24          * 由于(i+j)/2是向下取整，所以i+1=j时
25          * m=i，这个时候root的左子树为空
26          * */
27         if(m==i)
28                 root->left=NULL;
29         else
30                 root->left=Array2BST(array, i, m-1);
31         root->right=Array2BST(array, m+1, j);
32 
33         return root;
34 }

 

出题：要求实现函数：
　　size_t foo(unsigned int *a1, size_t a1l, unsigned int *a2, size_t a2l)
　　其中a1和a2都是无符号数组，a1l和a2l是对应数组的长度，并且都为偶数。
　　无符号数分成两个数字组成的多个数字区间，如下：
　　　　a1为0,1,3,8,10,20
　　　　a2为0,1,20,50,4,5
　　则a1表示的区间为[0,1],[3,8],[10,20]
　　则a2表示的区间为[0,1],[20,50],[4,5]
　　所以a1和a2重叠的部分为[0,1],[4,5]，长度为2
　　foo函数用于求给定区间数组a1和a2的重叠长度
　　注意：a1和a2长度不超过100万，并且同一个区间数组内部可能出现重叠

分析：

  • 线段树（Interval Tree）是BST的一种特例，它将一个区间划分成单元区间（最小元素），每个单元区间对应一个叶子节点；对于一个内部节点而言[a,b]，它的左子树节 点表示为[a,(a+b)/2]，它的右子树节点表示为[(a+b)/2+1,b]。由于每次划分都是对等划分所以IT为平衡树，最终子节点数为N（对于 整数区间而言就是所有数字分布的范围大小），深度为logN +1。快速确定某一个元素在哪些区间节点出现，时间复杂度为O(NlogN)，但是空间复杂度为O(N)；
  • 确定区间数组A和B中差值较小的的最大值m和最小值n（假设数组A的区间范围更小，O(A)），并构建区间[m,n]的线段树（O(AlogA)），这样 可以节省空间，如果区间范围较大，可以使用离散的建树方法针对区间元素出现的范围构建多棵区间树，或者使用压缩的方法减少区间节点；
  • 在线段树中标记在A中出现的区间节点（O(AlogA)）；将B的区间节点插入线段树（实际上并没有新节点的插入，只是检测是否有A标记过的节点），如果有A区间节点标记的节点，则说明有重复（O(BlogA)）。总时间复杂度O(AlogA)；

解题：

  1 struct Interval {
  2         int left;
  3         int right;
  4         int count;
  5 };
  6 /**
  7  * 此函数用于创建线段树的基本结构
  8  * */
  9 void ConstructIT(int min, int max, Interval** InterTree, int index) {
 10         /**
 11          * 构建当前节点
 12          * index用于索引InterTree中当前元素的位置
 13          * 遵循父节点为i，则做有子节点分别为2*i, 2*i+1
 14          * */
 15         Interval *temp=new Interval();
 16         temp->count=0;
 17         temp->left=min;
 18         temp->right=max;
 19         InterTree[index]=temp;
 20         /**
 21          * 如果min和max相等，则说明已经到叶子节点
 22          * */
 23         if(min==max)
 24                 return;
 25         /**
 26          * 分别递归创建左右子节点
 27          * */
 28         int middle=(min+max)/2;
 29         ConstructIT(min,middle,InterTree,index*2);
 30         ConstructIT(middle+1,max,InterTree,index*2+1);
 31 }
 32 /**
 33  * 此函数用于注入线段树的线段标记信息
 34  * */
 35 void InsertInfor(int min, int max, Interval** InterTree, int index) {
 36         int middle=(InterTree[index]->left + InterTree[index]->right)/2;
 37         if(max<middle) {
 38                 InsertInfor(min, max, InterTree, 2*index);
 39         } else if(min>middle) {
 40                 InsertInfor(min, max, InterTree, 2*index+1);
 41         } else if(min==InterTree[index]->left &&
 42                         max==InterTree[index]->right) {
 43                 InterTree[index]->count+=1;
 44                 return;
 45         } else {
 46                 InsertInfor(min, middle, InterTree, 2*index);
 47                 InsertInfor(middle+1, max, InterTree, 2*index+1);
 48         }
 49 }
 50 /**
 51  * 此函数用于检查覆盖区间，注意此时的min和max可能超出
 52  * InterTree的范围
 53  * */
 54 int CheckInterval(int min, int max, Interval** InterTree, int index) {
 55         int middle=(InterTree[index]->left + InterTree[index]->right)/2;
 56         if(max<middle) {
 57                 return CheckInterval(min, max, InterTree, 2*index);
 58         } else if(min>middle) {
 59                 return CheckInterval(min, max, InterTree, 2*index+1);
 60         } else if(min==InterTree[index]->left &&
 61                         max==InterTree[index]->right) {
 62                 if(InterTree[index]->count>0)
 63                         return InterTree[index]->count;
 64         } else {
 65                 CheckInterval(min, middle, InterTree, 2*index);
 66                 CheckInterval(middle+1, max, InterTree, 2*index+1);
 67         }
 68 }
 69 int GetOverlapSize(int *first, int lfirst, int *second, int lsecond) {
 70         /**
 71          * 获取first和second数组中各自的最大值与最小值的差值
 72          * 选取差值较小的一个范围作为线段树的构建区间
 73          * 节省空间消耗
 74          * */
 75         int minf=0, maxf=0,mins=0,maxs=0;
 76         for(int i=1;i<lfirst;i+=2) {
 77                 if(maxf<first[i])
 78                         maxf=first[i];
 79                 if(minf>first[i])
 80                         minf=first[i];
 81         }
 82         for(int i=1;i<lsecond;i+=2) {
 83                 if(maxs<second[i])
 84                         maxs=second[i];
 85                 if(mins>second[i])
 86                         mins=second[i];
 87         }
 88         int min=minf,max=maxf;
 89         int isFirst=true;
 90         if((max-min)>(maxs-mins)) {
 91                 min=mins;
 92                 max=maxs;
 93                 isFirst=false;
 94         }
 95         /**
 96          * 构建一个数组，数组元素为Interval*类型，
 97          * 数组大小为线段树节点个数，由于线段树是
 98          * 完全二叉树，所以节点数肯定为2N-1，N为区间
 99          * 大小，也为叶节点数
100          * */
101         Interval *InterTree[2*(max-min+1)-1];
102         /**
103          * 首先构建线段树的基本结构
104          * */
105         ConstructIT(min, max, InterTree, 0);
106         /**
107          * 然后将线段树范围大小对应的区间数组元素
108          * 插入到线段树中，如果区间在线段树之外则
109          * 需要特殊处理
110          * */
111         int *temp=NULL, length=0;
112         int overlapSize=0;
113         if(isFirst) {
114                 for(int i=1;i<lfirst;i+=2) {
115                         if(first[i]<InterTree[0]->left ||
116                                         first[i-1]>InterTree[0]->right)
117                                 continue;
118                         else if(first[i]==InterTree[0]->left ||
119                                         first[i-1]==InterTree[0]->right)
120                                 overlapSize++;
121                         else
122                                 InsertInfor(first[i-1],first[i], InterTree, 0);
123                 }
124                 temp=second;
125                 length=lsecond;
126         } else {
127                 for(int i=1;i<lsecond;i+=2) {
128                         if(second[i]<InterTree[0]->left ||
129                                         second[i-1]>InterTree[0]->right)
130                                 continue;
131                         else if(second[i]==InterTree[0]->left ||
132                                         second[i-1]==InterTree[0]->right)
133                                 overlapSize++;
134                         else
135                                 InsertInfor(second[i-1],second[i], InterTree, 0);
136                 }
137                 temp=first;
138                 length=lfirst;
139         }
140         /**
141          * 顺序将temp中的区间元素插入到InterTree中
142          * */
143 
144         for(int i=1;i<length;i+=2) {
145                 length+=CheckInterval(temp[i-1],temp[i],InterTree,0);
146         }
147 
148 }

 


联系
我们