新鲜出炉的腾讯后台开发三面面试题！

wzl7222504

弱弱的问一句
#define OFFSETOF(s, m) ((size_t) &((s *)0)->m);
其中
&((s *)0)->m中0表示啥，我没看懂

膜拜以下cjaizss版主，非常强大
希望您详细讲解下洗牌算法怎么算？2*54+rand()%2怎么算的？

XiaoLiangLinux

{:3_184:}

chenjuecj165

我好像都模棱两可，有的都不知道啊！这基础太差了！

ling0088

版主好强 学习

dynamic516

学习了

16887126

膜拜一下大大们

gigabyte

腾讯最近日子过得不错啊

bluecase

回复 118# 千年沉寂


    你的那个RandomPartition使得a[left : i-1] <= a <= a[i+1 : right].
怎么实现的？
对数组排序了吗？

bluecase

回复 113# 千年沉寂

[quote]
    可以的，平均时间达到O(n)

类似于二分法：
1.每次随机选取一个数 n，扫描一遍，使n 的左边都比 n小(l个元素)，右边都比 n 大(r 个元素)。
2.
    A:若满足条件，则返回n;
    B:若k>l,只对n右边的元素返回第一步执行;
    C:若k>r,只对n左边的元素返回第一步执行;

B,C每次只需执行一项，因此平均复杂度大概为：O(n+n/2+n/4...)=O(2n)=O(n)
[/quote］


每次随机选取一个数 n，扫描一遍，使n 的左边都比 n小(l个元素)，右边都比 n 大(r 个元素)。
随机取的数怎么能够实现左边比n小，有边比n大？？？
我估计是快排一样互相交换值了（100亿的话应该不行）.还是怎么去处理？

如果你的partition是参考快速排序的方法，这个partition是O(n)的时间复杂度。
所以这个最坏运行情况是O(n的平方)。而不是O（n）。

bluecase

回复  千年沉寂

[quote]
    可以的，平均时间达到O(n)

类似于二分法：
1.每次随机选取一个数 n， ...
bluecase 发表于 2010-07-12 13:41

    具体的可以参看算法导论里面的第9章。
    个人还是觉得像100亿如此的大数据查找，堆算法最好吧。