avatar
求 Paper. Help# Biology - 生物学
c*n
1
How will you find Nth largest pair (a[i], b[j]) from two sorted array A and
B
e.g.
A={10,8,5,3,2}
B={11,9,5,3}
Find 4th Largest pair gives: 9 + 8 = 17
Any nice solutions?
avatar
y*i
2
碟五纯粹从打斗和场面来看,没有蝶四好,但是超过前三部,而碟五最出彩的地方就是
重新回归了传统的剧情片,悬念片的概念,虽然没有第一部剧情那么曲折,但是绝对超
过2-4部的总体剧情设计,我想这也是这部最出彩的地方。
如果你想看大场面,这部电影勉强及格,开场部分真军飞机部分预告片里面都有,中间
就一个水下部分和摩托车追击算是大场面,但是如果拿出来单独比较的话,水下这场戏
略显简单,赶不上第一部密室部分,也赶不上上一部沙尘暴,摩托追击更赶不上吴宇森
。但是总体很好,阿汤哥在这些戏里面仍然可以信赖,潇洒不减当年。
最出彩的可能是对话和幽默,这部戏明显增强了Benji的戏份和Alex Baldwin以及
Brandt的幽默one liner,现场效果很好,反差很大,算是最幽默的一部,特别是最后
扮演英国首相的著名笑星更是出彩,steal every scene!
剧情无非是英国人不小心办了一个大错,试图掩盖,结果不行,只好劳动美国大哥出面
摆平,大哥很不乐意,只好顺便耍英国妹子,侮辱英国首相和MI6的boss。典型的好莱
坞思维,美国观众很受用。
另外一个,本剧的女主角戏份很足,可以说撑起了整部戏,超过以往所有女主角的戏份
总和,个人认为选角可以,这个演员有英气,有演技,比以前的paula强太多,对整部
戏的作用很大,完全可以期待在下部戏中继续露面,唯一缺点,身材太差,水下那场戏
把身材展现,象腿一览无余,忘记ps了。
另外,想不到这片子竟然是央视电影频道和阿里巴巴影视集团共同制作的,难怪里面没
有任何嘲笑中国和中国人的镜头,张静初在里面有正脸和一句台词,仅此而已,还有歌
剧图兰朵,中国市场应该不会差。
总体值得推荐,作为碟迷,可以满意!
avatar
w*e
3
Can anyone help me get a copy of following paper and send to my email:
w*****[email protected]
Thanks a lot. //bow.
A rapid method of calculating charge-charge interaction energies in proteins.
Pickersgill RW.
Protein Eng. 1988 Sep;2(3):247-8.
avatar
c*b
4
类似merge sort的最后一步?

and

【在 c*********n 的大作中提到】
: How will you find Nth largest pair (a[i], b[j]) from two sorted array A and
: B
: e.g.
: A={10,8,5,3,2}
: B={11,9,5,3}
: Find 4th Largest pair gives: 9 + 8 = 17
: Any nice solutions?

avatar
u*a
5
我觉得 paula 很有英气啊. 这种片不需要太多演技吧, 颜值高, 身材好就行了...

【在 y*******i 的大作中提到】
: 碟五纯粹从打斗和场面来看,没有蝶四好,但是超过前三部,而碟五最出彩的地方就是
: 重新回归了传统的剧情片,悬念片的概念,虽然没有第一部剧情那么曲折,但是绝对超
: 过2-4部的总体剧情设计,我想这也是这部最出彩的地方。
: 如果你想看大场面,这部电影勉强及格,开场部分真军飞机部分预告片里面都有,中间
: 就一个水下部分和摩托车追击算是大场面,但是如果拿出来单独比较的话,水下这场戏
: 略显简单,赶不上第一部密室部分,也赶不上上一部沙尘暴,摩托追击更赶不上吴宇森
: 。但是总体很好,阿汤哥在这些戏里面仍然可以信赖,潇洒不减当年。
: 最出彩的可能是对话和幽默,这部戏明显增强了Benji的戏份和Alex Baldwin以及
: Brandt的幽默one liner,现场效果很好,反差很大,算是最幽默的一部,特别是最后
: 扮演英国首相的著名笑星更是出彩,steal every scene!

avatar
w*e
6
bump!!
avatar
c*n
7
然后呢?你意思吧A and B 合并?
然后怎么找出 Nth largest pair啊?

【在 c*b 的大作中提到】
: 类似merge sort的最后一步?
:
: and

avatar
F*y
8
剧情确实不错,暑假难得的好片
avatar
c*b
9
弄个数组按降序记录pair的和
前N个都能找出来吧

【在 c*********n 的大作中提到】
: 然后呢?你意思吧A and B 合并?
: 然后怎么找出 Nth largest pair啊?

avatar
M*k
10
女主也太牛了,干掉了一号打手啊..
avatar
c*n
11
那还是O(n^2)啊

【在 c*b 的大作中提到】
: 弄个数组按降序记录pair的和
: 前N个都能找出来吧

avatar
y*i
12
这个女主不错,颜值可以,就是身材肥了点。演技也比paula好。
avatar
h*k
13
naive的方法是比较first n elements of A and first n elements of B, 得到n*n的
和,然后merge 找nth个,复杂度是O(n*n)
更好的方法是O(nlogn)
这个和是一个partial order,(x,y)表示A[x]+B[y],则
(0,0) > (0,1) > (0,2) >...
> > >
(1,0) > (1,1) > (1,2) >...
> > >
(2,0) > (2,1) > (2,2) >...
>
...
从(0,0)开始,把(0,0)存入heap of size n,
输出heap中的最大值,然后把(0,1)和(1,0)放入heap,再输出最大值。
suppose the maximum element in the heap is (i,j),remove it and insert( i+1,
j) and (i,j+1) into the heap. Count the output number.
有个问题,(i,j)可能会被放入heap

【在 c*********n 的大作中提到】
: How will you find Nth largest pair (a[i], b[j]) from two sorted array A and
: B
: e.g.
: A={10,8,5,3,2}
: B={11,9,5,3}
: Find 4th Largest pair gives: 9 + 8 = 17
: Any nice solutions?

avatar
l*d
14
"摩托追击更赶不上吴宇森"
个人感觉比吴宇森强多了这场摩托车追逐。只是这个导演不喜欢眩目拍法,动作戏摄影
都很平实。
这戏里的动作戏设计都很精心,比如刑讯那场的打斗。还有女主至少三次大腿缠脖,很
精彩。

【在 y*******i 的大作中提到】
: 碟五纯粹从打斗和场面来看,没有蝶四好,但是超过前三部,而碟五最出彩的地方就是
: 重新回归了传统的剧情片,悬念片的概念,虽然没有第一部剧情那么曲折,但是绝对超
: 过2-4部的总体剧情设计,我想这也是这部最出彩的地方。
: 如果你想看大场面,这部电影勉强及格,开场部分真军飞机部分预告片里面都有,中间
: 就一个水下部分和摩托车追击算是大场面,但是如果拿出来单独比较的话,水下这场戏
: 略显简单,赶不上第一部密室部分,也赶不上上一部沙尘暴,摩托追击更赶不上吴宇森
: 。但是总体很好,阿汤哥在这些戏里面仍然可以信赖,潇洒不减当年。
: 最出彩的可能是对话和幽默,这部戏明显增强了Benji的戏份和Alex Baldwin以及
: Brandt的幽默one liner,现场效果很好,反差很大,算是最幽默的一部,特别是最后
: 扮演英国首相的著名笑星更是出彩,steal every scene!

avatar
c*n
15
就是按照反对角线的顺序把元素放到heap是吧,恩好方法
但是细节好象还要考虑下,到底怎么输出Nth max,因为比如 4th的话
(2,0) (1,1) (0,2)都有可能的
所以我觉得O(N)应该就可以了吧?
因为找到相应的反对角线的第几行,然后比较那一行中的几个元素就可以了啊
但是给第一个N*N的Matrix,输入k,怎么得到是第几排呢?
比如k=4,是第3排,k=7 or 8 or 9 or 10是第4排

【在 h**k 的大作中提到】
: naive的方法是比较first n elements of A and first n elements of B, 得到n*n的
: 和,然后merge 找nth个,复杂度是O(n*n)
: 更好的方法是O(nlogn)
: 这个和是一个partial order,(x,y)表示A[x]+B[y],则
: (0,0) > (0,1) > (0,2) >...
: > > >
: (1,0) > (1,1) > (1,2) >...
: > > >
: (2,0) > (2,1) > (2,2) >...
: >

avatar
m*a
16
值得看3D么?
avatar
c*n
17

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~想了一下,用个for就可以,所以谢谢你的提示,我觉
得O(N)就可以找到了,如果有什么不对请指正

【在 c*********n 的大作中提到】
: 就是按照反对角线的顺序把元素放到heap是吧,恩好方法
: 但是细节好象还要考虑下,到底怎么输出Nth max,因为比如 4th的话
: (2,0) (1,1) (0,2)都有可能的
: 所以我觉得O(N)应该就可以了吧?
: 因为找到相应的反对角线的第几行,然后比较那一行中的几个元素就可以了啊
: 但是给第一个N*N的Matrix,输入k,怎么得到是第几排呢?
: 比如k=4,是第3排,k=7 or 8 or 9 or 10是第4排

avatar
m*a
18
暗黑中国女人,张静初那脸涂白的跟女鬼一样,和女主比天壤之别,完全符合
西方(包括国人)对国女的stereotype

【在 y*******i 的大作中提到】
: 碟五纯粹从打斗和场面来看,没有蝶四好,但是超过前三部,而碟五最出彩的地方就是
: 重新回归了传统的剧情片,悬念片的概念,虽然没有第一部剧情那么曲折,但是绝对超
: 过2-4部的总体剧情设计,我想这也是这部最出彩的地方。
: 如果你想看大场面,这部电影勉强及格,开场部分真军飞机部分预告片里面都有,中间
: 就一个水下部分和摩托车追击算是大场面,但是如果拿出来单独比较的话,水下这场戏
: 略显简单,赶不上第一部密室部分,也赶不上上一部沙尘暴,摩托追击更赶不上吴宇森
: 。但是总体很好,阿汤哥在这些戏里面仍然可以信赖,潇洒不减当年。
: 最出彩的可能是对话和幽默,这部戏明显增强了Benji的戏份和Alex Baldwin以及
: Brandt的幽默one liner,现场效果很好,反差很大,算是最幽默的一部,特别是最后
: 扮演英国首相的著名笑星更是出彩,steal every scene!

avatar
h*k
19

其实,这里(0,1)和(1,0)都有可能。比如
10,9,8,1
10,6,2,1
前第4个就是(0,0),(1,0),(2,0),(0,1)

【在 c*********n 的大作中提到】
: 就是按照反对角线的顺序把元素放到heap是吧,恩好方法
: 但是细节好象还要考虑下,到底怎么输出Nth max,因为比如 4th的话
: (2,0) (1,1) (0,2)都有可能的
: 所以我觉得O(N)应该就可以了吧?
: 因为找到相应的反对角线的第几行,然后比较那一行中的几个元素就可以了啊
: 但是给第一个N*N的Matrix,输入k,怎么得到是第几排呢?
: 比如k=4,是第3排,k=7 or 8 or 9 or 10是第4排

avatar
l*d
20
我没有看三地。看网上似乎有说三地还不不错的。

【在 m********a 的大作中提到】
: 值得看3D么?
avatar
s*t
21
和最小的n个pair,必定来自A0+Bi,Ai+B0, i=0,1,...,(n-1)这2n个数
这个不对吧?
avatar
m*h
22
没肌肉怎么打啊,还是一群猛男

【在 y*******i 的大作中提到】
: 这个女主不错,颜值可以,就是身材肥了点。演技也比paula好。
avatar
c*n
23
我也觉得这个存在严重bug
比如
A={10,8,1}
B={10,9,1}
4th 应该是8+9

【在 s*********t 的大作中提到】
: 和最小的n个pair,必定来自A0+Bi,Ai+B0, i=0,1,...,(n-1)这2n个数
: 这个不对吧?

avatar
m*d
24
有3d吗?电影院自己拿电脑处理的?

【在 l******d 的大作中提到】
: 我没有看三地。看网上似乎有说三地还不不错的。
avatar
c*n
25
你能不能详细解释下这个heap的用法?
到底需要存多少个元素进heap?并且是哪些元素?
如何解决一下的问题的:
A={10,9,8,7}
B={10,2,1,0}
找4th max,应该是10+7

【在 h**k 的大作中提到】
: naive的方法是比较first n elements of A and first n elements of B, 得到n*n的
: 和,然后merge 找nth个,复杂度是O(n*n)
: 更好的方法是O(nlogn)
: 这个和是一个partial order,(x,y)表示A[x]+B[y],则
: (0,0) > (0,1) > (0,2) >...
: > > >
: (1,0) > (1,1) > (1,2) >...
: > > >
: (2,0) > (2,1) > (2,2) >...
: >

avatar
g*5
26
女主身材不行,而且嘴是我最不喜欢那种“扁嘴”,不过从脱衣服那里看好像胸还够大。
最开始我以为那国女又是fbb或者lbb,完全不认识
avatar
b*v
27
假设Ai+Bj在和最小的n个pair里面,但是i和j都不等于0
那么我们把它换成A0+Bj或者Ai+B0,都能得到更小的数
所以在考虑完那2n个数之前,不必考虑i,j都不等于0的情形

【在 s*********t 的大作中提到】
: 和最小的n个pair,必定来自A0+Bi,Ai+B0, i=0,1,...,(n-1)这2n个数
: 这个不对吧?

avatar
c*t
28
没看到有3D的啊

【在 l******d 的大作中提到】
: 我没有看三地。看网上似乎有说三地还不不错的。
avatar
c*n
29
看不懂,举个反例吧:
A 1,2,10,100
B 1,3,20,200
最小的4个数为什么不包括 2+3呢?

【在 b******v 的大作中提到】
: 假设Ai+Bj在和最小的n个pair里面,但是i和j都不等于0
: 那么我们把它换成A0+Bj或者Ai+B0,都能得到更小的数
: 所以在考虑完那2n个数之前,不必考虑i,j都不等于0的情形

avatar
l*d
30
应该是imax

【在 c****t 的大作中提到】
: 没看到有3D的啊
avatar
g*1
31
how can you know A1+B1 is greater than A0+B4?

【在 b******v 的大作中提到】
: 假设Ai+Bj在和最小的n个pair里面,但是i和j都不等于0
: 那么我们把它换成A0+Bj或者Ai+B0,都能得到更小的数
: 所以在考虑完那2n个数之前,不必考虑i,j都不等于0的情形

avatar
m*y
32
同意。
另外没肌肉的大腿也缠不上脖呀。

【在 l******d 的大作中提到】
: "摩托追击更赶不上吴宇森"
: 个人感觉比吴宇森强多了这场摩托车追逐。只是这个导演不喜欢眩目拍法,动作戏摄影
: 都很平实。
: 这戏里的动作戏设计都很精心,比如刑讯那场的打斗。还有女主至少三次大腿缠脖,很
: 精彩。

avatar
g*1
33
Normally you have n*n matrix with columns and rows are sorted. You can merge
all columns at nlogn complexity.
avatar
c*n
34

`~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~我
之前的回复已经给反例了,你在看看?

【在 b******v 的大作中提到】
: 假设Ai+Bj在和最小的n个pair里面,但是i和j都不等于0
: 那么我们把它换成A0+Bj或者Ai+B0,都能得到更小的数
: 所以在考虑完那2n个数之前,不必考虑i,j都不等于0的情形

avatar
g*1
35
Normally you have n*n matrix with columns and rows are sorted. You can merge
all columns at nlogn complexity.
avatar
b*v
36
有道理,我错了

【在 c*********n 的大作中提到】
: 看不懂,举个反例吧:
: A 1,2,10,100
: B 1,3,20,200
: 最小的4个数为什么不包括 2+3呢?

avatar
g*1
37
how about this case?
size of A =4 and size of B =4
but the smallest 4 is: 1+1, 1+2,2+1 and 2+3 but 2+3 is not A0+Bi or Ai+B0
right?

【在 c*********n 的大作中提到】
: 看不懂,举个反例吧:
: A 1,2,10,100
: B 1,3,20,200
: 最小的4个数为什么不包括 2+3呢?

avatar
c*n
38

merge
~~~~~~~~~~~~~Can you show the algorithm?

【在 g**********1 的大作中提到】
: Normally you have n*n matrix with columns and rows are sorted. You can merge
: all columns at nlogn complexity.

avatar
y*n
39
你的假设在n小于Nth的N时成立。

【在 s*********t 的大作中提到】
: 和最小的n个pair,必定来自A0+Bi,Ai+B0, i=0,1,...,(n-1)这2n个数
: 这个不对吧?

avatar
X*n
40
assume A has n elements and B has m, and n<=m
then we can have n lists
a[0]+b[0]>=a[0]+b[1]>=......>=a[0]+b[m-1]
a[1]+b[0]>=a[1]+b[1]>=......>=a[1]+b[m-1]
.....
a[n-1]+b[0]>=................>=a[n-1]+b[m-1]
then we build a max-heap with the first element of each list with O(n).
delete the max from the heap and insert the next element from the
corresponding list, O(logn)
do it N times
So the complexity is O(Nlogn)

and

【在 c*********n 的大作中提到】
: How will you find Nth largest pair (a[i], b[j]) from two sorted array A and
: B
: e.g.
: A={10,8,5,3,2}
: B={11,9,5,3}
: Find 4th Largest pair gives: 9 + 8 = 17
: Any nice solutions?

avatar
c*n
41
恩,这个感觉是对的thanks

【在 X*********n 的大作中提到】
: assume A has n elements and B has m, and n<=m
: then we can have n lists
: a[0]+b[0]>=a[0]+b[1]>=......>=a[0]+b[m-1]
: a[1]+b[0]>=a[1]+b[1]>=......>=a[1]+b[m-1]
: .....
: a[n-1]+b[0]>=................>=a[n-1]+b[m-1]
: then we build a max-heap with the first element of each list with O(n).
: delete the max from the heap and insert the next element from the
: corresponding list, O(logn)
: do it N times

avatar
h*6
42
其实,对于多于两个数组的元素和或积排序,也可以用这个堆的办法。
avatar
u*s
43
This method looks like O(nlogn).
However, when you code it, you will notice that dedup is a little bit
annoying.
If you create a bitmap/boolean for n^2 and init to false, then this is
already n^2. Of course, you can use other hashtable to solve this, but just
looks ugly.
If you ignore this issue, then you can say this is O(nlogn) ...

【在 h**k 的大作中提到】
: naive的方法是比较first n elements of A and first n elements of B, 得到n*n的
: 和,然后merge 找nth个,复杂度是O(n*n)
: 更好的方法是O(nlogn)
: 这个和是一个partial order,(x,y)表示A[x]+B[y],则
: (0,0) > (0,1) > (0,2) >...
: > > >
: (1,0) > (1,1) > (1,2) >...
: > > >
: (2,0) > (2,1) > (2,2) >...
: >

avatar
b*7
44
The time complexity of building a n-element heap should be O(nlogn) because
inserting element needs O(logn).
avatar
X*n
45
heap building can be done in linear time, please check CLRS 6.3

because

【在 b*******7 的大作中提到】
: The time complexity of building a n-element heap should be O(nlogn) because
: inserting element needs O(logn).

avatar
h*6
46
这个容易,用STL中的set就可以解决。
定义一个priority_queue, vector >, greater > >
再定义一个set >
每次在set里面检查,如果没有就加入priority_queue,同时加入set。当从堆顶移除时
,也从set中删除。

just

【在 u**s 的大作中提到】
: This method looks like O(nlogn).
: However, when you code it, you will notice that dedup is a little bit
: annoying.
: If you create a bitmap/boolean for n^2 and init to false, then this is
: already n^2. Of course, you can use other hashtable to solve this, but just
: looks ugly.
: If you ignore this issue, then you can say this is O(nlogn) ...

avatar
h*k
47
你一共放入堆的数总数是n*n,最后是O(n*n*log)

【在 X*********n 的大作中提到】
: assume A has n elements and B has m, and n<=m
: then we can have n lists
: a[0]+b[0]>=a[0]+b[1]>=......>=a[0]+b[m-1]
: a[1]+b[0]>=a[1]+b[1]>=......>=a[1]+b[m-1]
: .....
: a[n-1]+b[0]>=................>=a[n-1]+b[m-1]
: then we build a max-heap with the first element of each list with O(n).
: delete the max from the heap and insert the next element from the
: corresponding list, O(logn)
: do it N times

avatar
h*k
48

heap本身大小不固定,就是一个max-heap,第一个放入的元素是10+10,
pop, 然后放入10+9,10+2,pop 10+9,放入10+8,然后pop 10+8,放入10+7

【在 c*********n 的大作中提到】
: 你能不能详细解释下这个heap的用法?
: 到底需要存多少个元素进heap?并且是哪些元素?
: 如何解决一下的问题的:
: A={10,9,8,7}
: B={10,2,1,0}
: 找4th max,应该是10+7

avatar
h*k
49
set本身是靠bst来实现的,每个查询/删除/插入都是O(logn),所以最好的数据结构这
里就是hash_table

pair

【在 h**6 的大作中提到】
: 这个容易,用STL中的set就可以解决。
: 定义一个priority_queue, vector >, greater: > >
: 再定义一个set >
: 每次在set里面检查,如果没有就加入priority_queue,同时加入set。当从堆顶移除时
: ,也从set中删除。
:
: just

avatar
b*v
50
又没有说要把所有的pair排序,只要找出前N个就行了,所以是O(N*log(n))

【在 h**k 的大作中提到】
: 你一共放入堆的数总数是n*n,最后是O(n*n*log)
avatar
c*p
51
(a[i], b[j]) 构成了young tableau.所以这个问题就是找young tableau第K大的元素.

and

【在 c*********n 的大作中提到】
: How will you find Nth largest pair (a[i], b[j]) from two sorted array A and
: B
: e.g.
: A={10,8,5,3,2}
: B={11,9,5,3}
: Find 4th Largest pair gives: 9 + 8 = 17
: Any nice solutions?

avatar
h*k
52
嗯,我搞错了。

【在 b******v 的大作中提到】
: 又没有说要把所有的pair排序,只要找出前N个就行了,所以是O(N*log(n))
avatar
h*k
53
嗯,我搞错了。

【在 b******v 的大作中提到】
: 又没有说要把所有的pair排序,只要找出前N个就行了,所以是O(N*log(n))
avatar
h*6
54
假设两个数组,各有1000000项
a[]={1000000, 999999, 999998, ..., 2, 1}
b[]={2000000, 1999999, 1999998, ..., 1000002, 1000001}
求第1000000大的ai+bj是多少,可以编程试试,看几秒钟能够出来。
avatar
h*6
55
写了个程序,执行时间半秒到一秒之间,结果是2998002,大家可以试一试。
#include
#include
#include
using namespace std;
const int N = 1000000;
const int M = 1000000;
inline void InsertHeapSet(int* a, int i, int* b, int j, priority_queueint, pair > >& Q, set >& S)
{
Q.push(pair >(a[i]+b[j], pair(i, j)));
S.insert(pair(i, j));
}
void main()
{
int* a = new int [N];
int* b = new int [N];
for(int i=0; i{


【在 h**6 的大作中提到】
: 假设两个数组,各有1000000项
: a[]={1000000, 999999, 999998, ..., 2, 1}
: b[]={2000000, 1999999, 1999998, ..., 1000002, 1000001}
: 求第1000000大的ai+bj是多少,可以编程试试,看几秒钟能够出来。

avatar
c*n
56
did u pass ur algo course ?

【在 X*********n 的大作中提到】
: heap building can be done in linear time, please check CLRS 6.3
:
: because

avatar
l*a
57
i think what he means is building a heap for a sorted array will cost
constant time.

【在 c******n 的大作中提到】
: did u pass ur algo course ?
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。