最近一直在面试，不时会被问到找无序数组中第k大元素的题。基本做法，看到过都是基于快排的partition思想的，时间复杂度虽然说平均O(n)，但是极端情况下会退化成O(n^2)。这个方法写起来不但很麻烦，复杂度方面也一直让我纠结，实在是一百万个不喜欢。
于是开始自己考虑别的解法。
传统的partition中最不好的地方是无法确定中位元的位置，也即难以将数组分成尽可能均等的两份。那么可不可以从别的角度来作划分呢？仔细思考后发现可以从bit方面作文章的。
假设数组存储的全部都是int类型的正整数（如果是long long或者有负数的情况也是类似的），从最高位开始，将所有该位为0的数放到数组的左面，将所有为1的数放到数组的右面，这显然是一个O(n)的划分过程。划分结果可以得到一个中间位置，其左面的数全部小于右边。到这里思路应该很清楚了：依次对更低的每一位重复该操作，就可以逐步逼近第k大的数。由于int正数最多只有31位，那么总的时间复杂度便是O(31n)的。虽然上界情况常数很大，但由于实际上不可能每次都扫遍整个数组的，所以实际的时间会比较接近O(n)。该算法还有很多其他好处，例如空间是O(1)的，也不存在退化的问题。
下面是实现代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n, m, a[10000000]; void init() { for(int i=0; i<n; i++) scanf("%d", a+i); } int partition(int a[], int n, int m, int b) { if(n==1) return a[0]; int i, j; for(i=0, j=n-1; i<j; ) { while(i<j && !(a[i]&b)) i++; while(i<j && (a[j]&b)) j--; if(i<j) swap(a[i], a[j]); } if(a[i]&b) i--; if(n-1-i>=m) { return partition(a+i+1, n-1-i, m, b>>1); } else { return partition(a, i+1, m-(n-1-i), b>>1); } } void solve() { printf("%d\n", partition(a, n, m, 1<<30)); } int main() { while(~scanf("%d%d", &n, &m)) { init(); solve(); } return 0; } |
不知道有没错呢，细心的人帮我看看好了。 =)
附送测试数据：
|
1 2 3 4 5 6 7 8 9 10 |
20 1 13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1 20 5 13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1 20 10 13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1 20 15 13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1 20 20 13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1 |
从此妈妈再也不用担心我不会解第k大元素啦！！！
ps：吐槽一下，竟然还有人写了这么长的文章来分析时间复杂度…能全部看完的人请一定来教育教育我。