Monthly Archives: September 2012

Coursera: Algorithms, Part I: Week 3

第三周的内容是归并排序和快速排序。视频里我不清楚的内容大多跟具体Java代码有关,我对Java没有兴趣所以不管了。讲的快排里有一点是比较有趣的:如果数组里有很多重复元素的话,经典的partition方法会很坏,极端情况就是如果元素全部相同,复杂度退化为平方级别。这个问题怎么解决呢,其实很简单,就是所谓3-way quick-sort,在partition时把数组分成小于、等于和大于pivot三部分,划分的方法实际上就是上一周最后的荷兰旗问题。然后只对小于和大于的两部分递归处理即可。这个复杂度和数组的熵成正比。

Interview Questions: MergeSort

3. Shuffle一个单链表,要求O(NlogN)时间,常数或O(logN)空间。

答:分治法。把一个链表分成两部分分别Shuffle,然后以各1/2的概率的决定哪部分在前面。 (感谢resty指出错误)在合并的时候,根据两部分的剩余长度动态决定下一个元素从哪一部分的头部取,设两部分长度分别为a和b,则以a/(a+b)的概率从第一部分取一个元素出来,持续此过程直至合并完毕。划分一个链表的复杂度是线性时间,合并两部分是常数时间,所以总时间复杂度就是O(NlogN)。递归需要的空间复杂度是O(logN)。具体实现的时候要注意记录每部分的头尾结点。

Interview Questions: QuickSort

1. 螺母和螺栓。有N个螺母和N个螺栓,每个螺母的大小都不同,每个螺栓的大小也都不同,对每个螺母有且仅有一个螺栓与它对应。每次你可以拿起一个螺母和一个螺栓比较,看看是否匹配,如果不匹配,显然你可以知道哪个大哪个小。但是不允许直接比较两个螺母或两个螺栓。现要求用最少的比较次数找出对应关系。

答:我曾在面试时被问到这个题。这个题很漂亮,不过出现在这一章后面就提示性太强了。方法就是类似快排,随便找一个螺母a,用它把所有螺栓分成小于a、大于a和等于a(只有一个)。再用那个等于a的螺栓把所有螺母也划分一遍。于是就得到了一对匹配和“大于a的螺母螺栓”、“小于a的螺母螺栓”两部分,递归处理。复杂度和随机选取pivot的快排的复杂度一样。

2. 给定两个排好序的数组a和b,长度分别为N1和N2,要找到第k大的数。复杂度应该是log(N1+N2)

答:先假设答案是a中,在a中二分查找,假设答案是a中的第x个数,则检查数组b中第k-x个元素及附近的元素,就可以确定二分查找的范围应该在前一半还是后一半。如果最后没有找到,则答案在数组b中,用同样过程颠倒ab再二分一遍。具体实现上有一些边界细节大概要比较注意才能写对。

3. 给定长度为N的数组,找出其中所有出现次数超过N/10的元素。复杂度是线性。

答:这是那个被出烂了的“找出出现超过一半的元素”的升级版。思路相同:如果我们每次找出10个不同的元素并删掉,直到找不出来为止,那么超过N/10次的那些元素一定会被剩下来。把这个思路用一个比较简单的方式实现出来:

struct Counter {int val, cnt;} counter[9];

for (k in A[]) {
  exist = False;
  for (i = 0 to 8) {
    if (counter[i].val == k) {++counter[i].cnt; exist = True; break;}
  }
  if (exist) continue;
  full = True;
  for (i = 0 to 8) {
    if (counter[i].cnt == 0) {counter[i].val = k; counter[i].cnt = 1; full = False; break;}
  }
  if (full) {
    for (i = 0 to 8) {--counter[i].cnt;}
  }
}

最后把所有剩下的counter[i].val检查一遍即可。