g*u
2 楼
一个nxm的matrix,每一行,每一列都是递增的,现找第k大个数,要求时间复杂度低于
O(mn)
O(mn)
z*6
3 楼
我可怜的菜娃娃到底是谁害s你们的啊?
b*0
4 楼
实验室一基因敲出小鼠,Het X Het 繁殖后代中,经genotyping鉴定为WT的老鼠中(换
了Genotyping方法同样),有些老鼠在蛋白水平上却是KO的。大家有木有遇到这情况?
了Genotyping方法同样),有些老鼠在蛋白水平上却是KO的。大家有木有遇到这情况?
M*k
5 楼
对。
z*6
7 楼
z*6
10 楼
b*0
11 楼
谢谢 解答。
但是 我们原先的方法是沿用大牛的genotyping方法,引物啥的都是大牛给的。一个偶
然的机会实验室发现了这个现象。于是我们又换了一种方法,自己设计引物检测,结果
与先前一样。
说实话,我们现在做了初步测序,貌似结果没啥,好似是一样的。下面将做mRNA水平看
看。先上来求求看看有没有高人支招。
但是 我们原先的方法是沿用大牛的genotyping方法,引物啥的都是大牛给的。一个偶
然的机会实验室发现了这个现象。于是我们又换了一种方法,自己设计引物检测,结果
与先前一样。
说实话,我们现在做了初步测序,貌似结果没啥,好似是一样的。下面将做mRNA水平看
看。先上来求求看看有没有高人支招。
i*e
16 楼
这年头, 你得花钱请 李昌钰,姓狄的已经死了。
D*a
17 楼
要是全套都做了还没有答案,就问大牛吧。
b*0
20 楼
脂肪组织, 做了16个样品中 有 4个样品有异常。
f*k
21 楼
没啥想法
b*n
24 楼
mark
c*p
25 楼
问过元芳了么? 他怎么看?
r*1
26 楼
呵呵,我想到点啥。【i,j】表示第 i row, 第 j column.我们给定m*n矩阵。
如果找最1个最大数,那就是最右下角【m,n】的数了;第2个最大数,就是min([m,n-1]
called A,[m-1,n] called B);
现在假设A给选中了。我们继续找第3个,就是min([m,n-2] called C,B); 注意,我们不
用比较【m-1,n-1】和[m-1,n](B),理由是同一行的右面的大。
如果我们假设B给选中了,我们继续找第3个,就是min(A,[m-2,n]);注意,我们不用比
较[m-1,n-1]和[m,n-1],理由就是同一列的下面的大。
规律就是从右下角开始顺着最下或最右两条边开始找,然后次最右或此最下,这样来找
那个k个最大的值。
我们访问每个元素仅一次,复杂度O(m*n)啦。
唉,不容易啊。好不容易发挥了一把。明天我面试,希望有如此发挥了。。。。。。
如果找最1个最大数,那就是最右下角【m,n】的数了;第2个最大数,就是min([m,n-1]
called A,[m-1,n] called B);
现在假设A给选中了。我们继续找第3个,就是min([m,n-2] called C,B); 注意,我们不
用比较【m-1,n-1】和[m-1,n](B),理由是同一行的右面的大。
如果我们假设B给选中了,我们继续找第3个,就是min(A,[m-2,n]);注意,我们不用比
较[m-1,n-1]和[m,n-1],理由就是同一列的下面的大。
规律就是从右下角开始顺着最下或最右两条边开始找,然后次最右或此最下,这样来找
那个k个最大的值。
我们访问每个元素仅一次,复杂度O(m*n)啦。
唉,不容易啊。好不容易发挥了一把。明天我面试,希望有如此发挥了。。。。。。
x*n
27 楼
还是个调嘴的,左边的菜怎么没动?
j*n
28 楼
没看懂
0 0 96
0 98 99
96 99 100
找第4大?
1]
【在 r**********1 的大作中提到】
: 呵呵,我想到点啥。【i,j】表示第 i row, 第 j column.我们给定m*n矩阵。
: 如果找最1个最大数,那就是最右下角【m,n】的数了;第2个最大数,就是min([m,n-1]
: called A,[m-1,n] called B);
: 现在假设A给选中了。我们继续找第3个,就是min([m,n-2] called C,B); 注意,我们不
: 用比较【m-1,n-1】和[m-1,n](B),理由是同一行的右面的大。
: 如果我们假设B给选中了,我们继续找第3个,就是min(A,[m-2,n]);注意,我们不用比
: 较[m-1,n-1]和[m,n-1],理由就是同一列的下面的大。
: 规律就是从右下角开始顺着最下或最右两条边开始找,然后次最右或此最下,这样来找
: 那个k个最大的值。
: 我们访问每个元素仅一次,复杂度O(m*n)啦。
0 0 96
0 98 99
96 99 100
找第4大?
1]
【在 r**********1 的大作中提到】
: 呵呵,我想到点啥。【i,j】表示第 i row, 第 j column.我们给定m*n矩阵。
: 如果找最1个最大数,那就是最右下角【m,n】的数了;第2个最大数,就是min([m,n-1]
: called A,[m-1,n] called B);
: 现在假设A给选中了。我们继续找第3个,就是min([m,n-2] called C,B); 注意,我们不
: 用比较【m-1,n-1】和[m-1,n](B),理由是同一行的右面的大。
: 如果我们假设B给选中了,我们继续找第3个,就是min(A,[m-2,n]);注意,我们不用比
: 较[m-1,n-1]和[m,n-1],理由就是同一列的下面的大。
: 规律就是从右下角开始顺着最下或最右两条边开始找,然后次最右或此最下,这样来找
: 那个k个最大的值。
: 我们访问每个元素仅一次,复杂度O(m*n)啦。
Z*I
29 楼
蜗牛或鼻涕虫。我家的被鼻涕虫啃完都这样,只有杆子没叶子。兔子更喜欢吃杆子。
T*n
30 楼
http://www.springerlink.com/content/ph106337753883w3/
http://www.math.tau.ac.il/~nogaa/PDFS/mono.pdf
这事到现在好像还没个定论呢
另外楼主问的是最坏复杂度还是平均复杂度?
http://www.math.tau.ac.il/~nogaa/PDFS/mono.pdf
这事到现在好像还没个定论呢
另外楼主问的是最坏复杂度还是平均复杂度?
b*f
32 楼
It looks like, those papers are talking about a more general problem.
a[i][j]In our case,
a[i][j]
【在 T**********n 的大作中提到】
: http://www.springerlink.com/content/ph106337753883w3/
: http://www.math.tau.ac.il/~nogaa/PDFS/mono.pdf
: 这事到现在好像还没个定论呢
: 另外楼主问的是最坏复杂度还是平均复杂度?
a[i][j]In our case,
a[i][j]
【在 T**********n 的大作中提到】
: http://www.springerlink.com/content/ph106337753883w3/
: http://www.math.tau.ac.il/~nogaa/PDFS/mono.pdf
: 这事到现在好像还没个定论呢
: 另外楼主问的是最坏复杂度还是平均复杂度?
j*l
36 楼
老杨,又见老杨。这是个著名的杨氏矩阵(Young Tableau), 集堆和BST的特性于一身。
j*l
38 楼
先解决如何在BST找第K大,肯定有启发。
n*7
39 楼
deer
c*p
42 楼
在young tableaux中找第K大元素可以参考在heap中找第k大元素,因为young tableaux
和heap有些类似.
while (count e = table.remove_min();
table.youngify(); //去掉最小元素后,调整结构以保持young tabuleaux特性,
count++;
}
return e;
youngify()与heapify()类似,通过shift元素来保持young tabuleaux特性, 其实现
可参考
http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf
for a table (m, n), youngify() 的复杂度:at most (m+n)
【在 g*****u 的大作中提到】
: 一个nxm的matrix,每一行,每一列都是递增的,现找第k大个数,要求时间复杂度低于
: O(mn)
和heap有些类似.
while (count
table.youngify(); //去掉最小元素后,调整结构以保持young tabuleaux特性,
count++;
}
return e;
youngify()与heapify()类似,通过shift元素来保持young tabuleaux特性, 其实现
可参考
http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf
for a table (m, n), youngify() 的复杂度:at most (m+n)
【在 g*****u 的大作中提到】
: 一个nxm的matrix,每一行,每一列都是递增的,现找第k大个数,要求时间复杂度低于
: O(mn)
P*5
43 楼
这么大的叶子不是slug了。
c*p
45 楼
鼻涕虫
s*9
47 楼
时间复杂度是O(n*lg(min(m,n))). 空间复杂度是O(min(m,n)).
c*n
49 楼
if extra memory is allowed, why not use external sorting. The complexity
would be O(k * min(n, m))
would be O(k * min(n, m))
i*b
51 楼
my approach:
given integer K, matrix A, 找出K的所有factor pairs whose product is K E.g:
K = 100
factor pairs:
(i, j)[] = (1, 100), (2, 50), (4, 25), (5, 20), (10, 10).
找A[i,j] and A[j, i]中最小的一个
given integer K, matrix A, 找出K的所有factor pairs whose product is K E.g:
K = 100
factor pairs:
(i, j)[] = (1, 100), (2, 50), (4, 25), (5, 20), (10, 10).
找A[i,j] and A[j, i]中最小的一个
m*g
53 楼
相关阅读
求文献假Jun Lu的真是身份到底是什么?Kg级发酵原料的价格以及发酵罐的价格查询常用的标记大肠杆菌的GFP和DSRED质粒有哪些生物wsn比化学强多了方舟子这么说,让我们的日子很难过!upright confocal 真讨厌大家快去Vote冰冻切片要看RFP自发荧光用什么固定Lu Jun 也是苦命人国内媒体披露卢俊(真Jun Lu) 和北化对陆骏造假反应 ( 转)写给Nature主编的抗议信这个就是所谓的“万人计划”吗?名单已经公示了,好快啊导师有抄袭我论文的嫌疑,怎么办贼心不死重投同一期刊应该注意点啥?为什么从一开始,所有人都认定是北化的lu jun造假而不是耶鲁的lu jun造假?mitbbs 生物版现在可能成了海外对中国最有影响力的网站板块造假处理刑不上大夫!RMB求美国大学paper下载账号或者agent权限。我觉得那个华人生物学家协会应该代表大家抗议那篇sb文章