L21 Balancing

Outline:

• 找前k大元素
• 找离medium最近的k个元素
• Weighted medium
• 找unique

Ref:

• 算法设计与分析(Algorithm design and analysis) by 黄宇

找前k大元素

（不是第k大）

• $nlogn$: 排序​
• $n+klogn$​​： 建堆，k次getMax
• $n+k^2$​​​​：建堆+从堆的前k层里面选k次（共有 $2^k$​​​个元素，对这个堆的fixHeap代价是$log{2}^k=k$​​​,找k次，即$k\times k$​）
• $n+klogk$: 先select出第k大的元素，代价$\mathrm{\Theta }(n)$；再以此为partition，对前k个元素排序，代价$\mathrm{\Theta }(klogk)$​

找离medium最近的k个元素

左界：$L=n/2-k$

右界: $R=n/2+k$

• 先 selcect(L)，找出左界的位置，然后partition（L）；对右界同理；最后对中间的部分做操作（方法有很多）

Weighted medium

$x_1,x_2,\dots ,x_n$​两两可比

$w_1,w_2,\dots ,w_n$, $w_i>0$​, ​ $\sum w_i=1$

找出weighted medium $x_k$​, 使得$\sum _{x_i<x_k}{w}_i<\frac{1}{2}$​, $ _{x_i > x_k} 2$（\mathrm{也}\mathrm{可}\mathrm{以}\mathrm{前}\mathrm{者}$$,\mathrm{后}\mathrm{者}$<$,\mathrm{但}\mathrm{不}\mathrm{能}\mathrm{二}\mathrm{者}\mathrm{都}\mathrm{是}$$​​）​

• $O(n)$: 先select得到medium（注意，不是 Weighted medium）； 再以此partition， 算出左右两边的weight，看哪边大于1/2，对子问题递归判断

找unique

所有元素只有一个和其他不一样，找出这个元素.

critical operation： compare（a, b）= Y ( a = b ) / N ( a != b)

• 可以用adversary argument 找出下界