请问房子后院和教堂的停车场只有一栅栏之隔有什么不好？ - 未名空间MITBBS历史存档

请问房子后院和教堂的停车场只有一栅栏之隔有什么不好？# Living

i*e2013-05-15 07:05

1 楼

Google(summer intern)
1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
，矩形的4个角都是1.
leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
意。不知道有没有复杂度更少的算法。
2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
目。之后把队打乱，
跟据高度和比自己高的人的数目还原原来的队列。
我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
算法。
Bloomberg:
1. 给一个数组： 6， 3， 10， 5， 16， 8， 4， 2， 1
找出这个数组的顺序。写一个程序，input是数组里的一个数，Output是从这个数开始
的整个数组。
2. 实现一个BFS算法。
3. 一个数组，里面有成对出现的数，也有单个的数，把单个的数找出来（leetcode原
题）。
4. 一个公司有好多员工，员工之间的关系储存为（employee ID, manager ID) 这样的
pair。要求写一个数据结构，储存这些员工之前的关系。
基于这样的数据结构写出：
1)查找employee的manager.
2)给一个employee和一个manager,查找这个manger是不是这个员工的直接或简介
manager(manager的manager这样的）
3)打印出一个manager手下所有的直接或者间接员工。
4）向这个数组里增加新的(employee, manager)关系。
并给出复杂度分析。
最后推荐一个算法群229623621,里面牛人很多，群里还自己做了OJ，讨论氛围很活跃。
发一些包子攒人品，期待好消息

G*W2013-05-15 07:05

2 楼

孩子的charisma , passionate , leadership, exploring the world这4种领䄂
character 极少有人提。。。
钢琴数学智商是这里的主流，我是个疯子，the floor is yours. I quit. I don't
belong to this forum .
除去了月光，除去了犀利哥，这是我的第五个马甲了，眼里都是酸楚的泪。。。内心是
一个
ghost town. 身为中国人，很悲伤。

h*12013-05-15 07:05

3 楼

我记得填写表格I－140EFILE 的表格时候，有地方询问配偶和孩子的信息，可是现在正
在填写的I－９０７没有地方看到询问配偶的信息，是不需要填写？还是配偶要额外填
一个I－９０７？
Many thanks

m*82013-05-15 07:05

4 楼

如题，特别是风水上有没有什么不好？生活上会很乱吗？多谢

j*e2013-05-15 07:05

5 楼

bless!

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

f*n2013-05-15 07:05

6 楼

哪位会配乐的帮一下，这个要是唱出来会很好听。
玩笑之后，我真心建议你专注做一个爱好，夏天钓鱼，冬天我就不知道了。

【在 G***W 的大作中提到】

: 孩子的charisma , passionate , leadership, exploring the world这4种领䄂
: character 极少有人提。。。
: 钢琴数学智商是这里的主流，我是个疯子，the floor is yours. I quit. I don't
: belong to this forum .
: 除去了月光，除去了犀利哥，这是我的第五个马甲了，眼里都是酸楚的泪。。。内心是
: 一个
: ghost town. 身为中国人，很悲伤。

h*12013-05-15 07:05

7 楼

UP, waiting online...

【在 h***1 的大作中提到】

: 我记得填写表格I－140EFILE 的表格时候，有地方询问配偶和孩子的信息，可是现在正
: 在填写的I－９０７没有地方看到询问配偶的信息，是不需要填写？还是配偶要额外填
: 一个I－９０７？
: Many thanks

s*a2013-05-15 07:05

8 楼

就是会比较吵而已。周日的时候，人多车多。

i*e2013-05-15 07:05

9 楼

谢谢。现在还在忧伤google summer intern的host match >.<

【在 j**********e 的大作中提到】

: bless!

N*62013-05-15 07:05

10 楼

夏天钓啥鱼？crappie 的季节我这儿是3月底到4月。。。。其它鱼我不懂习性。。
冬天可以滑雪，跑步。。。
今天听了老人建议多穿点，不能跟白妞一样，结果70度，气死人了。。太关心了，over
protection 不好。。

【在 f**********n 的大作中提到】

: 哪位会配乐的帮一下，这个要是唱出来会很好听。
: 玩笑之后，我真心建议你专注做一个爱好，夏天钓鱼，冬天我就不知道了。

i*t2013-05-15 07:05

11 楼

pp 和你孩子没啥关系
pp很简单主要就是写个收据号人家好对上你的case

J*e2013-05-15 07:05

12 楼

good luck

h*12013-05-15 07:05

13 楼

谢谢泡泡糖！！那我现在就填了

c*f2013-05-15 07:05

14 楼

求问google第一题解法

i*t2013-05-15 07:05

15 楼

907上要你写啥你就写啥
没有的不用考虑啊

【在 h***1 的大作中提到】

: 谢谢泡泡糖！！那我现在就填了

l*a2013-05-15 07:05

16 楼

thanks for sharing
群里的OJ上线了？赶紧去看看

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

l*t2013-05-15 07:05

17 楼

bless

G*s2013-05-15 07:05

18 楼

Bless!
求问google第二题O(NlogN)的算法谢谢

l*y2013-05-15 07:05

19 楼

Bless

h*52013-05-15 07:05

20 楼

请教一下google第二题，我的想法是按每个人手里的数字排序，然后再逐步插入，请问
你是怎么做的

R*d2013-05-15 07:05

21 楼

bless

w*m2013-05-15 07:05

22 楼

G的第二题是不是身高不能重复？

a*j2013-05-15 07:05

23 楼

bless!

d*02013-05-15 07:05

24 楼

bless

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

l*a2013-05-15 07:05

25 楼

1) sort
2) 对于最矮的人，你还知道前面比他高的有几个。这样你就知道了他的位置
然后找第二矮的，你还知道前面比他高的有几个。你还知道最矮的人在哪里，就因
该可以确定第2矮的位置
然后类推

【在 G*****s 的大作中提到】

: Bless!
: 求问google第二题O(NlogN)的算法谢谢

i*e2013-05-15 07:05

26 楼

我也是这么做的

【在 h********5 的大作中提到】

: 请教一下google第二题，我的想法是按每个人手里的数字排序，然后再逐步插入，请问
: 你是怎么做的

i*e2013-05-15 07:05

27 楼

是的

【在 w****m 的大作中提到】

: G的第二题是不是身高不能重复？

f*n2013-05-15 07:05

28 楼

bless

l*a2013-05-15 07:05

29 楼

bless

J*o2013-05-15 07:05

30 楼

其实关键在于确定第i个人的位置的时候，因为剩下的都是比他高的，而已经确定位置
的都是比他矮的，只要保证他前面有和原排序前面比他高的人数量相等的空位即可。如
果直接扫空位的话是O(N^2)。快一点的方法是把剩下的空位段保存在interval tree里
，这样每次找第k个空位只要O(logN)，总体的复杂度是O(NlogN)

【在 l*****a 的大作中提到】

: 1) sort
: 2) 对于最矮的人，你还知道前面比他高的有几个。这样你就知道了他的位置
: 然后找第二矮的，你还知道前面比他高的有几个。你还知道最矮的人在哪里，就因
: 该可以确定第2矮的位置
: 然后类推

l*a2013-05-15 07:05

31 楼

需要那么复杂吗？
sort完了，一个个插入相应位置不就可以了

【在 J***o 的大作中提到】

: 其实关键在于确定第i个人的位置的时候，因为剩下的都是比他高的，而已经确定位置
: 的都是比他矮的，只要保证他前面有和原排序前面比他高的人数量相等的空位即可。如
: 果直接扫空位的话是O(N^2)。快一点的方法是把剩下的空位段保存在interval tree里
: ，这样每次找第k个空位只要O(logN)，总体的复杂度是O(NlogN)

l*52013-05-15 07:05

32 楼

bless

k*62013-05-15 07:05

33 楼

按身高排序 NlogN，然后按身高顺序问数，linear time重现元队列，所以只要NlogN。
解释：
最高的人(P0)站哪里都无所谓，因为他记得数是一定是0.
所以直接问身高第二的人(P1)，如果是0站P0前面，如果是1站P0后面。
再问身高第三的人，。。。。
这题不难，我是不是说太细了，汗。

【在 h********5 的大作中提到】

: 请教一下google第二题，我的想法是按每个人手里的数字排序，然后再逐步插入，请问
: 你是怎么做的

k*62013-05-15 07:05

34 楼

刚看到lolhaha的方法，从最矮的开始直接定位，更节省space，赞。

NlogN。

【在 k********6 的大作中提到】

: 按身高排序 NlogN，然后按身高顺序问数，linear time重现元队列，所以只要NlogN。
: 解释：
: 最高的人(P0)站哪里都无所谓，因为他记得数是一定是0.
: 所以直接问身高第二的人(P1)，如果是0站P0前面，如果是1站P0后面。
: 再问身高第三的人，。。。。
: 这题不难，我是不是说太细了，汗。

J*o2013-05-15 07:05

35 楼

就是sort完一个个插入啊。。。问题是你怎么得到"相应位置"，虽然表达起来很直观。
interval tree可以O(logN)。

【在 l*****a 的大作中提到】

: 需要那么复杂吗？
: sort完了，一个个插入相应位置不就可以了

i*r2013-05-15 07:05

36 楼

这是phone interview的题目还是onsite，phone interview一个小时内能把两个题的
code写完吗？

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

p*d2013-05-15 07:05

37 楼

Bless..

F*g2013-05-15 07:05

38 楼

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

f*n2013-05-15 07:05

39 楼

mark

n*c2013-05-15 07:05

40 楼

说一下第一题矩阵的思路，抛砖引玉。
把矩阵的每行看成一个int
每行和其他行与，得到N^2/2个结果
设与的结果为m，则任一m如果有两个以上bit为1，则存在这个矩形。
O(1)时间判断m是否两个以上bit为1
如果m==0，则0个bit为1
如果m只有一个bit为1，则是2的n次幂，满足m&(m-1)==0
所以只要m!=0 && m&(m-1)!=0，m必有两个以上bit为1
所以整体解法复杂度是O(N^2)

J*o2013-05-15 07:05

41 楼

这个只有一行大小<=32的时候才能O(N^2)吧。复杂度应该是O(N^2 * N/32)，相当于降
低了常数项，整体复杂度没变。不知道有没有更优的解法。。

【在 n******c 的大作中提到】

: 说一下第一题矩阵的思路，抛砖引玉。
: 把矩阵的每行看成一个int
: 每行和其他行与，得到N^2/2个结果
: 设与的结果为m，则任一m如果有两个以上bit为1，则存在这个矩形。
: O(1)时间判断m是否两个以上bit为1
: 如果m==0，则0个bit为1
: 如果m只有一个bit为1，则是2的n次幂，满足m&(m-1)==0
: 所以只要m!=0 && m&(m-1)!=0，m必有两个以上bit为1
: 所以整体解法复杂度是O(N^2)

m*k2013-05-15 07:05

42 楼

你想说O(N^2 * （N－32）)吧？

【在 J***o 的大作中提到】

: 这个只有一行大小<=32的时候才能O(N^2)吧。复杂度应该是O(N^2 * N/32)，相当于降
: 低了常数项，整体复杂度没变。不知道有没有更优的解法。。

m*k2013-05-15 07:05

43 楼

同求楼主说的leecode上类似解法。

【在 c****f 的大作中提到】

: 求问google第一题解法

m*k2013-05-15 07:05

44 楼

记下每行为1的indexes,
和另一行的indexes
求交，结果集>1即可。还是O(N^3), :(

【在 J***o 的大作中提到】

: 这个只有一行大小<=32的时候才能O(N^2)吧。复杂度应该是O(N^2 * N/32)，相当于降
: 低了常数项，整体复杂度没变。不知道有没有更优的解法。。

M*t2013-05-15 07:05

45 楼

伊昔太仆张景顺
喜气自能成岁丰
酒开新瓮鲊开包
一等孔门为弟子
昨日嘉鱼来访我
后会未期心的的
朝来自觉承恩最
但是人家有遗爱

A*a2013-05-15 07:05

46 楼

bless

m*t2013-05-15 07:05

47 楼

去哪个了。

h*k2013-05-15 07:05

48 楼

bless

a*q2013-05-15 07:05

49 楼

Bless

w*22013-05-15 07:05

50 楼

Chi

w*a2013-05-15 07:05

51 楼

Bless

h*22013-05-15 07:05

52 楼

bless

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

w*c2013-05-15 07:05

53 楼

big bless

P*92013-05-15 07:05

54 楼

多谢！祝楼主拿到offer！

s*h2013-05-15 07:05

55 楼

niu

w*s2013-05-15 07:05

56 楼

第二题不是heap sort么？

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

v*y2013-05-15 07:05

57 楼

小庭新扫地
手种未全成
一回终宴喜
伸屈须看蠖
包胥心独许
子夜最可怜
来朝大将稀

f*r2013-05-15 07:05

58 楼

Mark.

x*l2013-05-15 07:05

59 楼

bless！！！吃包子！！！

h*l2013-05-15 07:05

60 楼

天街雪似盐
芟庭留野菜
掘壕不到水
豁然逢光晶
但和大小包

d*r2013-05-15 07:05

61 楼

Bless

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

n*r2013-05-15 07:05

62 楼

应该可以重复吧？
貌似不影响

【在 i*********e 的大作中提到】

: 是的

n*r2013-05-15 07:05

63 楼

google 第一题，可以是O(n*m)的时间的。但需要 O(n^2)的空间，（假设n<=m)

b*f2013-05-15 07:05

64 楼

bless

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

w*32013-05-15 07:05

65 楼

求O（n*m）的解法？

【在 n********r 的大作中提到】

: google 第一题，可以是O(n*m)的时间的。但需要 O(n^2)的空间，（假设n<=m)

S*e2013-05-15 07:05

66 楼

请问interval tree 如何使用可以详细说说吗？
谢谢！

【在 J***o 的大作中提到】

: 其实关键在于确定第i个人的位置的时候，因为剩下的都是比他高的，而已经确定位置
: 的都是比他矮的，只要保证他前面有和原排序前面比他高的人数量相等的空位即可。如
: 果直接扫空位的话是O(N^2)。快一点的方法是把剩下的空位段保存在interval tree里
: ，这样每次找第k个空位只要O(logN)，总体的复杂度是O(NlogN)

y*k2013-05-15 07:05

67 楼

bless，我也申请了很多intern，都没下文

w*e2013-05-15 07:05

68 楼

bless

f*y2013-05-15 07:05

69 楼

bless

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

z*d2013-05-15 07:05

70 楼

bless

n*o2013-05-15 07:05

71 楼

BLESS

d*12013-05-15 07:05

72 楼

bless

s*d2013-05-15 07:05

73 楼

吃

l*u2013-05-15 07:05

74 楼

bless

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

b*e2013-05-15 07:05

75 楼

For G1 O(n^2):
map[][] = 0; // map[i][j] records whether line i and line j have two
positions overlapping as 1s
for (i = 0; i < n; i++) {
currentOnes = []; // currentOnes is list of all the 1s that are
discovered so far on column i.
for (j = 0; j < m; j++) {
if (A[i][j] == 1) {
for (k = 0; k < currentOnes.length; k++) {
map[currentOnes[k]][j]++;
if (map[currentOnes[k]][j] > 2) {
return true;
}
currentOnes.push(j);
}
}
}
}
return false;

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

d*y2013-05-15 07:05

76 楼

zan

z*h2013-05-15 07:05

77 楼

这个不是O(n^2) 吧

★ 发自iPhone App: ChineseWeb 7.8

【在 b***e 的大作中提到】

: For G1 O(n^2):
: map[][] = 0; // map[i][j] records whether line i and line j have two
: positions overlapping as 1s
: for (i = 0; i < n; i++) {
: currentOnes = []; // currentOnes is list of all the 1s that are
: discovered so far on column i.
: for (j = 0; j < m; j++) {
: if (A[i][j] == 1) {
: for (k = 0; k < currentOnes.length; k++) {
: map[currentOnes[k]][j]++;

F*g2013-05-15 07:05

78 楼

bless

【在 i*********e 的大作中提到】

: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。

b*e2013-05-15 07:05

79 楼

仔细看。最内层循环amortize O (1) , because every cell in map [][] will be
set at most twice.

【在 z******h 的大作中提到】

: 这个不是O(n^2) 吧
:
: ★ 发自iPhone App: ChineseWeb 7.8