Y**G
发帖数: 1089 | 1 假设有个数组，元素是数，未排序。要求给出排49%到51%之间的任何一个数字。假设49
%和51%是指从小到大的排列次序。要求时间复杂度是O(N)，N是数组的长度。 |
j*****g
发帖数: 254 | |
Y**G
发帖数: 1089 | 3 N x log(N)是不行地
【在 j*****g 的大作中提到】
: quick sort
|
g**********y
发帖数: 1 | |
z*******o
发帖数: 4773 | 5 fine kth element in array.
平均O(n)
理论上O(n)的超出考试范围, algorithm书上有. |
c*******a
发帖数: 1879 | 6 quick sort O(nlogn)
quick select O(n)
【在 j*****g 的大作中提到】
: quick sort
|
X******g
发帖数: 10 | 7 quick select
49
【在 Y**G 的大作中提到】
: 假设有个数组，元素是数，未排序。要求给出排49%到51%之间的任何一个数字。假设49
: %和51%是指从小到大的排列次序。要求时间复杂度是O(N)，N是数组的长度。
|
z*********n
发帖数: 1451 | 8 lz题目被版友们秒了，该版平均刷题水平越来越高了，世风日下啊。。。 |
y**********u
发帖数: 2839 | 9 zeng兄此言差矣，众位基友的水平日益提高，都是拜PXJ所赐啊，来，和我一起喊：
刷X转X，工资XX！
【在 z*********n 的大作中提到】
: lz题目被版友们秒了，该版平均刷题水平越来越高了，世风日下啊。。。
|
z*******o
发帖数: 4773 | 10 然并卵, 结果就是公司bar不断提高.
【在 z*********n 的大作中提到】
: lz题目被版友们秒了，该版平均刷题水平越来越高了，世风日下啊。。。
|
|
|
Y**G
发帖数: 1089 | 11 正解
【在 z*******o 的大作中提到】
: fine kth element in array.
: 平均O(n)
: 理论上O(n)的超出考试范围, algorithm书上有.
|
Y**G
发帖数: 1089 | 12 这种东西，如果事先不知道，当场想出来的才算高手。刷出来的不算。
【在 Y**G 的大作中提到】
: 正解
|
y**********u
发帖数: 2839 | 13 所以才要平时多做题
【在 Y**G 的大作中提到】
: 这种东西，如果事先不知道，当场想出来的才算高手。刷出来的不算。
|
z*********n
发帖数: 1451 | 14
所以我说的是世风日下。。
【在 z*******o 的大作中提到】
: 然并卵, 结果就是公司bar不断提高.
|
r*******n
发帖数: 395 | 15 两周前去面试碰到类似的题目 （一个搜素系统有N个搜素输入 找出最小SUB SET
CONTAINING 5%的搜素） 临时想出用quickSORT 的partition， 但写代码还是不太熟练 |
M***6
发帖数: 895 | 16 这种要求O（n）达到的数组操作一般都是hash。。 |
g**f
发帖数: 38 | 17 居然真有面试要现场写quicksort/quickselect，很复杂啊
[在 rubberban (小笨猪) 的大作中提到：]
:两周前去面试碰到类似的题目 （一个搜素系统有N个搜素输入 找出最小SUB SET
:CONTAINING 5%的搜素） 临时想出用quickSORT 的partition， 但写代码还是不太熟练 |
z*********n
发帖数: 1451 | 18
熟练
不至于，quickselect在现在面试都属于送分题级别的（不用median of median做初选
的话，用的话也就是是个medium难度）。
我N年前面实习就写的quicksort。上回面某家也写了quickselect。问的是一堆3D点
到原点距离第K近的，15分钟秒杀了。这题放LC应该是中下甚至easy吧。
【在 g**f 的大作中提到】
: 居然真有面试要现场写quicksort/quickselect，很复杂啊
: [在 rubberban (小笨猪) 的大作中提到：]
: :两周前去面试碰到类似的题目 （一个搜素系统有N个搜素输入 找出最小SUB SET
: :CONTAINING 5%的搜素） 临时想出用quickSORT 的partition， 但写代码还是不太熟练
|
z*********n
发帖数: 1451 | 19
此言差矣，刷题本身就是学习的过程，学到的知识当然就是自己的了。就跟我问你直角
三角形勾3股4，请问弦多少？你莫非说知道勾股定理的不算，必须是自己亲手推出来勾
股定理的才算？
老兄一句：如果道事先不知，当场想出来的才算高手。刷出来的不算，不知道否定了多
少ACMer（包括各种金牌神牛）几千个小时的努力学习。。
【在 Y**G 的大作中提到】
: 这种东西，如果事先不知道，当场想出来的才算高手。刷出来的不算。
|
