Coursera: Algorithms, Part I: Week 4

前段时间事情较多,所以进度跟不上了,我会尽快把剩下的补完。

第四周的内容是优先队列和二叉搜索树。只记得最后提到,如果用普通的BST(非平衡的)进行随机的插入和删除,期望复杂度会是O(sqrt(N)),这个我之前倒是不知道,只知道故意构造的最坏情况会变成O(N)。已经不记得有什么其它的有趣的点了,直接看题目吧。

Interview Questions: Priority Queue

1. 设计一个表示动态集合的数据结构,使得插入元素是对数时间,查询中位数是常数时间,删除中位数是对数时间。

答:实际上我见过一道类似的ACM题。我们假定在集合中有偶数个元素时,中位数是指较小的那个中间数。用两个堆,一个大顶堆包含集合里较小的(N+1)/2个数,另一个小顶堆包含集合里较大的另一半数。查询中位数时,直接看大顶堆的堆顶元素即可。插入元素时,先将其与两个堆顶元素比较,以决定插入哪个堆。如果插入之后两堆的元素个数之差超过了1,就把多的那个堆的堆顶元素插入到另一堆里。删除元素时,将中位数删掉之后,同样调整两个堆的元素个数。

2. 设计一个优先队列,支持两种额外操作:随机访问队列里一个元素,随机删除队列里一个元素。

答:因为堆用连续的一段数组表示,随机访问只需要随机得到一个[0,N-1]之间的数组下标即可。随机删除元素和删除堆顶元素其实是一样的,把最后一个元素放到被删除的元素的位置,然后把它向下沉直到合适为止。

3. 找出所有的四元组(a,b,c,d),满足a^3+b^3=c^3+d^3 (a,b,c,d <= N)。要求O(N^2*logN)的时间,O(N)的空间。

答:先看另外一道很有趣的问题:给定两个排好序的数组A和B,两数组长度都为N,我们从两个数组各取一个元素求和,这样就得到了N^2个和,要求把这N^2个和按序输出,空间不能超过O(N)。方法是建立一个堆,开始时堆中的元素A[1]+B[1], A[1]+B[2], …, A[1]+B[N],每次从堆中取最小元素输出,然后看看这个元素是怎么来的,假设是A[i]+B[j],就把A[i+1]+B[j]插入堆。回到本问题,现在只是A,B数组都是1^3, 2^3, … N^3而已,用同样算法,如果发现相邻两次输出的值相同,说明找到了一组解。空间显然是O(N),因为共输出N^2个元素,每次堆操作是O(logN),所以时间是O(N^2*logN)

Interview Questions: Elementary Symbol Table

2. 判断一个树是否是BST。要求使用O(h)的空间,h是树的高度。

答:

int check(Node *p, int low, int high) {
  if (low > high) return 0;
  if (p == NULL) return 1;
  return check(p->left, low, p->value) && check(p->right, p->value, high);  
}
  1. treap 就是利用随机插入删除期望是logN嘛。

    第二个,那个随机访问的意思我估计不是随便找一个?而是像是一个数组1~n,我可能要找第k个,也可能要找最大的什么的?类似dijkstra加堆优化那种形式,可能修改某一个点的路径和取最近的点,修改就是随机访问

  2. 第2个题,堆中元素的删除;最后一个元素放到被删除的元素的位置后,可能是需要上浮而不是下沉。

  3. 人生不过三万天,成功失败均坦然,是非恩怨莫在意,健康快乐最值钱。

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>