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 楼
对。
D*C
6 楼
感觉是应该先根据k的值先确定落在哪条逆对角线上，然后在这条斜线上搜索
【在 g*****u 的大作中提到】
: 一个nxm的matrix，每一行，每一列都是递增的，现找第k大个数，要求时间复杂度低于
: O(mn)
【在 g*****u 的大作中提到】
: 一个nxm的matrix，每一行，每一列都是递增的，现找第k大个数，要求时间复杂度低于
: O(mn)
z*6
7 楼
O*e
8 楼
最大的可能是你基因型鉴定出了问题。这种情况，光靠PCR是解决不了问题了。建议
直接做Southern blot；或者做SB之前做一下RT-PCR看一下mRNA表达的变化。
【在 b*******0 的大作中提到】
: 实验室一基因敲出小鼠，Het X Het 繁殖后代中，经genotyping鉴定为WT的老鼠中（换
: 了Genotyping方法同样），有些老鼠在蛋白水平上却是KO的。大家有木有遇到这情况？
直接做Southern blot；或者做SB之前做一下RT-PCR看一下mRNA表达的变化。
【在 b*******0 的大作中提到】
: 实验室一基因敲出小鼠，Het X Het 繁殖后代中，经genotyping鉴定为WT的老鼠中（换
: 了Genotyping方法同样），有些老鼠在蛋白水平上却是KO的。大家有木有遇到这情况？
r*o
9 楼
同问。
还有一道题是对这个matrix排序，用什么算法最好?
【在 g*****u 的大作中提到】
: 一个nxm的matrix，每一行，每一列都是递增的，现找第k大个数，要求时间复杂度低于
: O(mn)
还有一道题是对这个matrix排序，用什么算法最好?
【在 g*****u 的大作中提到】
: 一个nxm的matrix，每一行，每一列都是递增的，现找第k大个数，要求时间复杂度低于
: O(mn)
z*6
10 楼
b*0
11 楼
谢谢 解答。
但是 我们原先的方法是沿用大牛的genotyping方法，引物啥的都是大牛给的。一个偶
然的机会实验室发现了这个现象。于是我们又换了一种方法，自己设计引物检测，结果
与先前一样。
说实话，我们现在做了初步测序，貌似结果没啥，好似是一样的。下面将做mRNA水平看
看。先上来求求看看有没有高人支招。
但是 我们原先的方法是沿用大牛的genotyping方法，引物啥的都是大牛给的。一个偶
然的机会实验室发现了这个现象。于是我们又换了一种方法，自己设计引物检测，结果
与先前一样。
说实话，我们现在做了初步测序，貌似结果没啥，好似是一样的。下面将做mRNA水平看
看。先上来求求看看有没有高人支招。
j*n
12 楼
既然每行都排好序了，用归并怎么样？
【在 r****o 的大作中提到】
: 同问。
: 还有一道题是对这个matrix排序，用什么算法最好?
【在 r****o 的大作中提到】
: 同问。
: 还有一道题是对这个matrix排序，用什么算法最好?
T*m
13 楼
兔子和蜗牛的可能性大一些。
【在 z***6 的大作中提到】
: 我可怜的菜娃娃到底是谁害s你们的啊？
【在 z***6 的大作中提到】
: 我可怜的菜娃娃到底是谁害s你们的啊？
O*e
14 楼
你用啥组织做的WB？几个样品？
【在 b*******0 的大作中提到】
: 谢谢 解答。
: 但是 我们原先的方法是沿用大牛的genotyping方法，引物啥的都是大牛给的。一个偶
: 然的机会实验室发现了这个现象。于是我们又换了一种方法，自己设计引物检测，结果
: 与先前一样。
: 说实话，我们现在做了初步测序，貌似结果没啥，好似是一样的。下面将做mRNA水平看
: 看。先上来求求看看有没有高人支招。
【在 b*******0 的大作中提到】
: 谢谢 解答。
: 但是 我们原先的方法是沿用大牛的genotyping方法，引物啥的都是大牛给的。一个偶
: 然的机会实验室发现了这个现象。于是我们又换了一种方法，自己设计引物检测，结果
: 与先前一样。
: 说实话，我们现在做了初步测序，貌似结果没啥，好似是一样的。下面将做mRNA水平看
: 看。先上来求求看看有没有高人支招。
D*h
15 楼
简单归并不行，时间上为O(n^3).
【在 j***n 的大作中提到】
: 既然每行都排好序了，用归并怎么样？
【在 j***n 的大作中提到】
: 既然每行都排好序了，用归并怎么样？
i*e
16 楼
这年头， 你得花钱请 李昌钰，姓狄的已经死了。
D*a
17 楼
要是全套都做了还没有答案，就问大牛吧。
j*n
18 楼
哦，复杂度是有点儿高，不过应该是O(n^2 * lg(n))吧
【在 D***h 的大作中提到】
: 简单归并不行，时间上为O(n^3).
【在 D***h 的大作中提到】
: 简单归并不行，时间上为O(n^3).
f*g
19 楼
李昌钰是谁？你的真名么？
【在 i*******e 的大作中提到】
: 这年头， 你得花钱请 李昌钰，姓狄的已经死了。
【在 i*******e 的大作中提到】
: 这年头， 你得花钱请 李昌钰，姓狄的已经死了。
b*0
20 楼
脂肪组织, 做了16个样品中 有 4个样品有异常。
f*k
21 楼
没啥想法
y*8
22 楼
真惨！上个CHICKEN WIRE把菜地围起来吧，要不没法种菜了。
【在 z***6 的大作中提到】
: 我可怜的菜娃娃到底是谁害s你们的啊？
【在 z***6 的大作中提到】
: 我可怜的菜娃娃到底是谁害s你们的啊？
O*e
23 楼
以后再取组织，找一个这个基因表达很强的组织作为阳性对照来做WB或者染色。
【在 b*******0 的大作中提到】
: 脂肪组织, 做了16个样品中 有 4个样品有异常。
【在 b*******0 的大作中提到】
: 脂肪组织, 做了16个样品中 有 4个样品有异常。
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
这事到现在好像还没个定论呢
另外楼主问的是最坏复杂度还是平均复杂度？
z*6
31 楼
会不会是松鼠?
【在 Z***I 的大作中提到】
: 蜗牛或鼻涕虫。我家的被鼻涕虫啃完都这样，只有杆子没叶子。兔子更喜欢吃杆子。
【在 Z***I 的大作中提到】
: 蜗牛或鼻涕虫。我家的被鼻涕虫啃完都这样，只有杆子没叶子。兔子更喜欢吃杆子。
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
: 这事到现在好像还没个定论呢
: 另外楼主问的是最坏复杂度还是平均复杂度？
z*6
33 楼
是惨到家了，老爸好不容易在老乡那拿了3棵红苔菜指望可以留种结果全军覆没:-(
【在 y*****8 的大作中提到】
: 真惨！上个CHICKEN WIRE把菜地围起来吧，要不没法种菜了。
【在 y*****8 的大作中提到】
: 真惨！上个CHICKEN WIRE把菜地围起来吧，要不没法种菜了。
r*1
34 楼
谢谢提醒，我的算法有问题。
【在 j***n 的大作中提到】
: 没看懂
: 0 0 96
: 0 98 99
: 96 99 100
: 找第4大？
:
: 1]
【在 j***n 的大作中提到】
: 没看懂
: 0 0 96
: 0 98 99
: 96 99 100
: 找第4大？
:
: 1]
z*6
35 楼
偶是大农村的农妇，二耳不闻村外事一心只想抓真凶，元芳请指点哈
【在 f******g 的大作中提到】
: 李昌钰是谁？你的真名么？
【在 f******g 的大作中提到】
: 李昌钰是谁？你的真名么？
j*l
36 楼
老杨，又见老杨。这是个著名的杨氏矩阵(Young Tableau), 集堆和BST的特性于一身。
z*6
37 楼
xs56
【在 f******g 的大作中提到】
: 李昌钰是谁？你的真名么？
【在 f******g 的大作中提到】
: 李昌钰是谁？你的真名么？
j*l
38 楼
先解决如何在BST找第K大，肯定有启发。
n*7
39 楼
deer
x*3
40 楼
每个节点中保存子树大小
【在 j**l 的大作中提到】
: 先解决如何在BST找第K大，肯定有启发。
【在 j**l 的大作中提到】
: 先解决如何在BST找第K大，肯定有启发。
B*a
41 楼
可能是蝴蝶干的
【在 z***6 的大作中提到】
【在 z***6 的大作中提到】
c*p
42 楼
在young tableaux中找第K大元素可以参考在heap中找第k大元素，因为young tableaux
和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)
和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了。
b*v
44 楼
thanks!
tableaux
【在 c***p 的大作中提到】
: 在young tableaux中找第K大元素可以参考在heap中找第k大元素，因为young tableaux
: 和heap有些类似.
: while (count
: table.youngify(); //去掉最小元素后，调整结构以保持young tabuleaux特性，
: count++;
: }
: return e;
: youngify()与heapify()类似，通过shift元素来保持young tabuleaux特性， 其实现
: 可参考
tableaux
【在 c***p 的大作中提到】
: 在young tableaux中找第K大元素可以参考在heap中找第k大元素，因为young tableaux
: 和heap有些类似.
: while (count
: table.youngify(); //去掉最小元素后，调整结构以保持young tabuleaux特性，
: count++;
: }
: return e;
: youngify()与heapify()类似，通过shift元素来保持young tabuleaux特性， 其实现
: 可参考
c*p
45 楼
鼻涕虫
s*9
46 楼
应该是 O(n*lgn)吧。
【在 j***n 的大作中提到】
: 哦，复杂度是有点儿高，不过应该是O(n^2 * lg(n))吧
【在 j***n 的大作中提到】
: 哦，复杂度是有点儿高，不过应该是O(n^2 * lg(n))吧
s*9
47 楼
时间复杂度是O(n*lg(min(m,n))). 空间复杂度是O(min(m,n)).
w*0
48 楼
How about selection algorithm?
for random N size , array, find kth big number will only take O(N)
for matrix, it only has mn size, so take O(MN)
【在 g*****u 的大作中提到】
: 一个nxm的matrix，每一行，每一列都是递增的，现找第k大个数，要求时间复杂度低于
: O(mn)
for random N size , array, find kth big number will only take O(N)
for matrix, it only has mn size, so take O(MN)
【在 g*****u 的大作中提到】
: 一个nxm的matrix，每一行，每一列都是递增的，现找第k大个数，要求时间复杂度低于
: O(mn)
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))
g*u
50 楼
你怎么做？如果二分查找，剩下的两块丧失了young matrix的特性。
用每次取出一个最小的方法，需要O(mn(m+n))超过了O(mn)的要求。
用merge sort需要O(mn log(min(m,n)),也超过了，还要用extra mem。
【在 x******3 的大作中提到】
: 每个节点中保存子树大小
用每次取出一个最小的方法，需要O(mn(m+n))超过了O(mn)的要求。
用merge sort需要O(mn log(min(m,n)),也超过了，还要用extra mem。
【在 x******3 的大作中提到】
: 每个节点中保存子树大小
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]中最小的一个
b*v
52 楼
如果8x8矩阵里找第13大的数，就只找(1,13)和(13,1)吗？
【在 i**********b 的大作中提到】
: 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]中最小的一个
【在 i**********b 的大作中提到】
: 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]中最小的一个
m*g
53 楼
这样就是O(k*(m+n))的复杂度了
tableaux
【在 c***p 的大作中提到】
: 在young tableaux中找第K大元素可以参考在heap中找第k大元素，因为young tableaux
: 和heap有些类似.
: while (count
: table.youngify(); //去掉最小元素后，调整结构以保持young tabuleaux特性，
: count++;
: }
: return e;
: youngify()与heapify()类似，通过shift元素来保持young tabuleaux特性， 其实现
: 可参考
tableaux
【在 c***p 的大作中提到】
: 在young tableaux中找第K大元素可以参考在heap中找第k大元素，因为young tableaux
: 和heap有些类似.
: while (count
: table.youngify(); //去掉最小元素后，调整结构以保持young tabuleaux特性，
: count++;
: }
: return e;
: youngify()与heapify()类似，通过shift元素来保持young tabuleaux特性， 其实现
: 可参考
相关阅读
求今年ICIBM share hotel room请教：双侧海马内微量注射抗体后小鼠几乎全部死亡韩长的像说相声韩副主席因为断电，重复不了，其实也没什么要是韩春雨能重复出来，那还真是挺好的Xiaole Shirley Liu at Harvard问个promoter问题推荐几个常用的文献管理软件和文献追踪软件植物-动物-生态-神经生物-信息-水产专业海归高校机会这个稿子撤的有点滑稽请教一个基因的问题主要责任处在那个公司的产品质量太差警惕一些会议为啥没有能从中间切断脂肪酸的酶？请问一套小动物遥测系统大概多少钱？Genetron Health (泛生子) ：2016年中国最具投资价值企业50强 (转载)miss颜最大的错误是结论下的太早了International Liar Championship of 2016请教Chip-seq的问题2016目前为止分子细胞生物学的最重大突破