发个一直没有见过满意答案的题吧# JobHunting - 待字闺中
w*x
1 楼
Given an array with all elements sorted on each individual row and column
find the K-th smallest one
有个做法是用heap, 但好像也不是很合适...
find the K-th smallest one
有个做法是用heap, 但好像也不是很合适...
f*e
2 楼
复杂度要求呢？
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
C*U
3 楼
你是说给定一个matrix 是么?
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
l*c
4 楼
我怎么觉得用heap挺好的呢，worst case n^2, 但一般用不到那么多吧
c*r
5 楼
复杂度klogk， worst case是 n^2 log n, 跟直接sort是一样的
【在 l****c 的大作中提到】
: 我怎么觉得用heap挺好的呢，worst case n^2, 但一般用不到那么多吧
【在 l****c 的大作中提到】
: 我怎么觉得用heap挺好的呢，worst case n^2, 但一般用不到那么多吧
l*8
6 楼
我记得一个解法是从左下角出发，
while (1) {
if （target == element） {
return found;
} else if （target > element） {
if (can move ritht)
move right;
else
return notFound;
} else { // target < element
if (can move up)
move up;
else
return notFound；
};
这个算法O(n+m) time, where n is row number and m is the column number. 你觉
得这个方法太慢了？
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
while (1) {
if （target == element） {
return found;
} else if （target > element） {
if (can move ritht)
move right;
else
return notFound;
} else { // target < element
if (can move up)
move up;
else
return notFound；
};
这个算法O(n+m) time, where n is row number and m is the column number. 你觉
得这个方法太慢了？
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
l*c
7 楼
大哥，直接sort和k无关，heap至少还用的k吧
【在 c*****r 的大作中提到】
: 复杂度klogk， worst case是 n^2 log n, 跟直接sort是一样的
【在 c*****r 的大作中提到】
: 复杂度klogk， worst case是 n^2 log n, 跟直接sort是一样的
C*U
8 楼
你应该把题目再看一边
【在 l*********8 的大作中提到】
: 我记得一个解法是从左下角出发，
: while (1) {
: if （target == element） {
: return found;
: } else if （target > element） {
: if (can move ritht)
: move right;
: else
: return notFound;
: } else { // target < element
【在 l*********8 的大作中提到】
: 我记得一个解法是从左下角出发，
: while (1) {
: if （target == element） {
: return found;
: } else if （target > element） {
: if (can move ritht)
: move right;
: else
: return notFound;
: } else { // target < element
c*r
9 楼
我的意思是heap算法的worst case 和sort的worst case复杂度是一样的。
其实两个方法的average case复杂度也是一样的，都是n^2 logn
我说的average指的是k是在1-n^2之间uniform选取。
大哥，直接sort和k无关，heap至少还用的k吧
【在 l****c 的大作中提到】
: 大哥，直接sort和k无关，heap至少还用的k吧
其实两个方法的average case复杂度也是一样的，都是n^2 logn
我说的average指的是k是在1-n^2之间uniform选取。
大哥，直接sort和k无关，heap至少还用的k吧
【在 l****c 的大作中提到】
: 大哥，直接sort和k无关，heap至少还用的k吧
l*c
10 楼
这个是在matrix找数
【在 l*********8 的大作中提到】
: 我记得一个解法是从左下角出发，
: while (1) {
: if （target == element） {
: return found;
: } else if （target > element） {
: if (can move ritht)
: move right;
: else
: return notFound;
: } else { // target < element
【在 l*********8 的大作中提到】
: 我记得一个解法是从左下角出发，
: while (1) {
: if （target == element） {
: return found;
: } else if （target > element） {
: if (can move ritht)
: move right;
: else
: return notFound;
: } else { // target < element
l*c
11 楼
我昨天才巩固的heap，可能理解还是不深吧。
sort在这个matrix的worstcase是不是n^2 logn^2啊？总数量是n^2，不是n。
heap只要k！=n^2就比sort好吧。复杂度是n^2 logk/
具体操作，从最小的那端数k个，开始和max heap的root比，按行走，如果大于root的
话，直接跳到下一行，应该很快的。
【在 c*****r 的大作中提到】
: 我的意思是heap算法的worst case 和sort的worst case复杂度是一样的。
: 其实两个方法的average case复杂度也是一样的，都是n^2 logn
: 我说的average指的是k是在1-n^2之间uniform选取。
:
: 大哥，直接sort和k无关，heap至少还用的k吧
sort在这个matrix的worstcase是不是n^2 logn^2啊？总数量是n^2，不是n。
heap只要k！=n^2就比sort好吧。复杂度是n^2 logk/
具体操作，从最小的那端数k个，开始和max heap的root比，按行走，如果大于root的
话，直接跳到下一行，应该很快的。
【在 c*****r 的大作中提到】
: 我的意思是heap算法的worst case 和sort的worst case复杂度是一样的。
: 其实两个方法的average case复杂度也是一样的，都是n^2 logn
: 我说的average指的是k是在1-n^2之间uniform选取。
:
: 大哥，直接sort和k无关，heap至少还用的k吧
l*8
12 楼
哦，是finad the kth smallest one.
thanks!
【在 C***U 的大作中提到】
: 你应该把题目再看一边
thanks!
【在 C***U 的大作中提到】
: 你应该把题目再看一边
l*8
13 楼
恩，看错了。 楼主是要在matrix里find the K-th smallest one
【在 l****c 的大作中提到】
: 这个是在matrix找数
【在 l****c 的大作中提到】
: 这个是在matrix找数
e*s
14 楼
这个好像是找某个数，不是第k个。
【在 l*********8 的大作中提到】
: 我记得一个解法是从左下角出发，
: while (1) {
: if （target == element） {
: return found;
: } else if （target > element） {
: if (can move ritht)
: move right;
: else
: return notFound;
: } else { // target < element
【在 l*********8 的大作中提到】
: 我记得一个解法是从左下角出发，
: while (1) {
: if （target == element） {
: return found;
: } else if （target > element） {
: if (can move ritht)
: move right;
: else
: return notFound;
: } else { // target < element
l*c
15 楼
话说，面试会让写heap代码不？
K*n
16 楼
我觉得实现不太可能吧，percolate up和percolate down什么的。直接用没什么的。
当然实现其实也不难，我觉得应该是需要掌握的内容。
【在 l****c 的大作中提到】
: 话说，面试会让写heap代码不？
当然实现其实也不难，我觉得应该是需要掌握的内容。
【在 l****c 的大作中提到】
: 话说，面试会让写heap代码不？
l*c
17 楼
嗯，原理不难，就是怕要是让现场写，没写过的话，像我这种档次的估计会崩溃了。
【在 K*********n 的大作中提到】
: 我觉得实现不太可能吧，percolate up和percolate down什么的。直接用没什么的。
: 当然实现其实也不难，我觉得应该是需要掌握的内容。
【在 K*********n 的大作中提到】
: 我觉得实现不太可能吧，percolate up和percolate down什么的。直接用没什么的。
: 当然实现其实也不难，我觉得应该是需要掌握的内容。
K*n
18 楼
基本数据结构实现一遍，两天够了
【在 l****c 的大作中提到】
: 嗯，原理不难，就是怕要是让现场写，没写过的话，像我这种档次的估计会崩溃了。
【在 l****c 的大作中提到】
: 嗯，原理不难，就是怕要是让现场写，没写过的话，像我这种档次的估计会崩溃了。
d*g
19 楼
用heap可以做到O(k^2)吧~
l*8
20 楼
k = 1/2 * n^2的时候（中位数）。 O(k^2) 就是O(n^4).
【在 d*********g 的大作中提到】
: 用heap可以做到O(k^2)吧~
【在 d*********g 的大作中提到】
: 用heap可以做到O(k^2)吧~
w*x
21 楼
表示还没看到满意答案, 呼唤two爷~~~~
l*8
22 楼
Given: n by m matrix A,
k
定义
int low[n]; // low[i]是在第i行查找的下限
int high[n]; // high[i]是在第i行查找的上限
low数组初始为全0， high全部是m.
取一个pivot (比如第n/2行的第k/n个元素), 在每行的low[i]和high[i]元素范围中找
该pivot对应的upper boundary，存为pos[i].
num = sum( pos[i] - low[i] | for all i) 就是比pivot小的element的数目。
if (num == k-1) {
return pivot;
} else if (num > k-1) {
// 把high数组（查找上限）update为pos数组的值。
// 在新的low,high范围内递归查找k-th smallest element
} else { // num < k-1
// 把low数组（查找下限）update为pos数组的值。
// 在新的low,high范围内递归查找（k-num）-th smallest element
}
每轮更新low or high数组是O(n+m) time,
总共O(log(n*m))轮。
总的时间复杂度 O( (n+m)*log(n*m) )
如果n==m， 就是O( 4* n* logn), 也就是O(n*logn)
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
k
定义
int low[n]; // low[i]是在第i行查找的下限
int high[n]; // high[i]是在第i行查找的上限
low数组初始为全0， high全部是m.
取一个pivot (比如第n/2行的第k/n个元素), 在每行的low[i]和high[i]元素范围中找
该pivot对应的upper boundary，存为pos[i].
num = sum( pos[i] - low[i] | for all i) 就是比pivot小的element的数目。
if (num == k-1) {
return pivot;
} else if (num > k-1) {
// 把high数组（查找上限）update为pos数组的值。
// 在新的low,high范围内递归查找k-th smallest element
} else { // num < k-1
// 把low数组（查找下限）update为pos数组的值。
// 在新的low,high范围内递归查找（k-num）-th smallest element
}
每轮更新low or high数组是O(n+m) time,
总共O(log(n*m))轮。
总的时间复杂度 O( (n+m)*log(n*m) )
如果n==m， 就是O( 4* n* logn), 也就是O(n*logn)
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
l*8
23 楼
关于boundary，可能还有bug。 但大概思路就是这样。
【在 l*********8 的大作中提到】
: Given: n by m matrix A,
: k
: 定义
: int low[n]; // low[i]是在第i行查找的下限
: int high[n]; // high[i]是在第i行查找的上限
: low数组初始为全0， high全部是m.
: 取一个pivot (比如第n/2行的第k/n个元素), 在每行的low[i]和high[i]元素范围中找
: 该pivot对应的upper boundary，存为pos[i].
: num = sum( pos[i] - low[i] | for all i) 就是比pivot小的element的数目。
: if (num == k-1) {
【在 l*********8 的大作中提到】
: Given: n by m matrix A,
: k
: 定义
: int low[n]; // low[i]是在第i行查找的下限
: int high[n]; // high[i]是在第i行查找的上限
: low数组初始为全0， high全部是m.
: 取一个pivot (比如第n/2行的第k/n个元素), 在每行的low[i]和high[i]元素范围中找
: 该pivot对应的upper boundary，存为pos[i].
: num = sum( pos[i] - low[i] | for all i) 就是比pivot小的element的数目。
: if (num == k-1) {
d*s
24 楼
是这样的矩阵么？
1 3 5
2 7 8
6 9 11
如果是的话，可以按照/分层，每层都比上一层大，比如第一层是1，第二层是2,3,第三
层6 7 5等等
对于NxN矩阵中第k个最小的数字，所处的层数n由max n for k-n*(n+1)/2>0得到，然后
对该层(n+1)所有数字排序，复杂度nlog(n)，取第int(k-n*(n+1)/2)个，得到结果
1 3 5
2 7 8
6 9 11
如果是的话，可以按照/分层，每层都比上一层大，比如第一层是1，第二层是2,3,第三
层6 7 5等等
对于NxN矩阵中第k个最小的数字，所处的层数n由max n for k-n*(n+1)/2>0得到，然后
对该层(n+1)所有数字排序，复杂度nlog(n)，取第int(k-n*(n+1)/2)个，得到结果
l*8
25 楼
可能是这样的矩阵：
1 6 10
2 8 11
6 9 12
照/分层不总是成立。
【在 d*s 的大作中提到】
: 是这样的矩阵么？
: 1 3 5
: 2 7 8
: 6 9 11
: 如果是的话，可以按照/分层，每层都比上一层大，比如第一层是1，第二层是2,3,第三
: 层6 7 5等等
: 对于NxN矩阵中第k个最小的数字，所处的层数n由max n for k-n*(n+1)/2>0得到，然后
: 对该层(n+1)所有数字排序，复杂度nlog(n)，取第int(k-n*(n+1)/2)个，得到结果
1 6 10
2 8 11
6 9 12
照/分层不总是成立。
【在 d*s 的大作中提到】
: 是这样的矩阵么？
: 1 3 5
: 2 7 8
: 6 9 11
: 如果是的话，可以按照/分层，每层都比上一层大，比如第一层是1，第二层是2,3,第三
: 层6 7 5等等
: 对于NxN矩阵中第k个最小的数字，所处的层数n由max n for k-n*(n+1)/2>0得到，然后
: 对该层(n+1)所有数字排序，复杂度nlog(n)，取第int(k-n*(n+1)/2)个，得到结果
d*s
26 楼
确实理解有问题
【在 l*********8 的大作中提到】
: 可能是这样的矩阵：
: 1 6 10
: 2 8 11
: 6 9 12
: 照/分层不总是成立。
【在 l*********8 的大作中提到】
: 可能是这样的矩阵：
: 1 6 10
: 2 8 11
: 6 9 12
: 照/分层不总是成立。
h*l
27 楼
N = 行数
M = 列数
k - 第k个
X = Min(k, NM - k) // k 和 NM - k 的最小值
Y = Min(N, M) // 行数和列数的最小值
复杂度： O( X log(Y))
ok, 算法如下，假设行数少，k 比 NM - k 小
取第一列， 做一个heap， 插入 , 即 数值 和 哪一行的数值
ExtractMin() 取出堆里头最小的那个
到rowID 取出下一个，插入堆中
如此反复直到第 k 个 ExtractMin() 得到的就是第 k 个数
END
堆的大小一直都是行数 （如果列数少，就是列数， 因为行列都排好序了， 所以哪个
方向都可以）
想不出 O(k) 的方法了， 我觉得再变态也得至少看到头k个数吧。 所以我觉得这个O(
k log(行数)) 的复杂度已经差不多够低的了
M = 列数
k - 第k个
X = Min(k, NM - k) // k 和 NM - k 的最小值
Y = Min(N, M) // 行数和列数的最小值
复杂度： O( X log(Y))
ok, 算法如下，假设行数少，k 比 NM - k 小
取第一列， 做一个heap， 插入
ExtractMin() 取出堆里头最小的那个
到rowID 取出下一个，插入堆中
如此反复直到第 k 个 ExtractMin() 得到的就是第 k 个数
END
堆的大小一直都是行数 （如果列数少，就是列数， 因为行列都排好序了， 所以哪个
方向都可以）
想不出 O(k) 的方法了， 我觉得再变态也得至少看到头k个数吧。 所以我觉得这个O(
k log(行数)) 的复杂度已经差不多够低的了
f*4
28 楼
heap做法指的是出(i,j)入(i+1,j)和(i,j+1)？
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
w*x
29 楼
恩
【在 f*******4 的大作中提到】
: heap做法指的是出(i,j)入(i+1,j)和(i,j+1)？
l*8
30 楼
怎样保证元素不重复入heap?
【在 w****x 的大作中提到】
:
: 恩
【在 w****x 的大作中提到】
:
: 恩
c*t
31 楼
感觉需要一个structure, 除了value 还需要 i, j
heap顺序只比较value，入的时候还要判断i,j,去掉重复插入。还真的需要写一个
customized heap啊。
【在 l*********8 的大作中提到】
: 怎样保证元素不重复入heap?
heap顺序只比较value，入的时候还要判断i,j,去掉重复插入。还真的需要写一个
customized heap啊。
【在 l*********8 的大作中提到】
: 怎样保证元素不重复入heap?
l*8
32 楼
我觉得写成n个arrays merge那种heap方便些，不用考虑矩阵元素重复进入heap的问题。
【在 c********t 的大作中提到】
: 感觉需要一个structure, 除了value 还需要 i, j
: heap顺序只比较value，入的时候还要判断i,j,去掉重复插入。还真的需要写一个
: customized heap啊。
【在 c********t 的大作中提到】
: 感觉需要一个structure, 除了value 还需要 i, j
: heap顺序只比较value，入的时候还要判断i,j,去掉重复插入。还真的需要写一个
: customized heap啊。
c*t
33 楼
不错，感觉这个解法很优化了。
突然闪现一道很多马赛马的智力题，没有秒表的情况下，最少次数得到前三名，就是这
么解得。
【在 h*******l 的大作中提到】
: N = 行数
: M = 列数
: k - 第k个
: X = Min(k, NM - k) // k 和 NM - k 的最小值
: Y = Min(N, M) // 行数和列数的最小值
: 复杂度： O( X log(Y))
: ok, 算法如下，假设行数少，k 比 NM - k 小
: 取第一列， 做一个heap， 插入 , 即 数值 和 哪一行的数值
: ExtractMin() 取出堆里头最小的那个
: 到rowID 取出下一个，插入堆中
突然闪现一道很多马赛马的智力题，没有秒表的情况下，最少次数得到前三名，就是这
么解得。
【在 h*******l 的大作中提到】
: N = 行数
: M = 列数
: k - 第k个
: X = Min(k, NM - k) // k 和 NM - k 的最小值
: Y = Min(N, M) // 行数和列数的最小值
: 复杂度： O( X log(Y))
: ok, 算法如下，假设行数少，k 比 NM - k 小
: 取第一列， 做一个heap， 插入
: ExtractMin() 取出堆里头最小的那个
: 到rowID 取出下一个，插入堆中
c*t
34 楼
n个arrays merge的heap, 和一个数一个数插入heap复杂度是不是一样啊？
既然排好序的，直接merge 也是O(n*m)
题。
【在 l*********8 的大作中提到】
: 我觉得写成n个arrays merge那种heap方便些，不用考虑矩阵元素重复进入heap的问题。
既然排好序的，直接merge 也是O(n*m)
题。
【在 l*********8 的大作中提到】
: 我觉得写成n个arrays merge那种heap方便些，不用考虑矩阵元素重复进入heap的问题。
g*e
35 楼
young tableau. O(K * (m+n)) time, O(1) space
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
l*8
36 楼
hydrofuel的方法就相当于n arrays merge. 只不过到第k个数就结束了，而且前k-1个
数也不用保存。
【在 c********t 的大作中提到】
: n个arrays merge的heap, 和一个数一个数插入heap复杂度是不是一样啊？
: 既然排好序的，直接merge 也是O(n*m)
:
: 题。
数也不用保存。
【在 c********t 的大作中提到】
: n个arrays merge的heap, 和一个数一个数插入heap复杂度是不是一样啊？
: 既然排好序的，直接merge 也是O(n*m)
:
: 题。
c*t
37 楼
是的，明白你的意思了。
【在 l*********8 的大作中提到】
: hydrofuel的方法就相当于n arrays merge. 只不过到第k个数就结束了，而且前k-1个
: 数也不用保存。
【在 l*********8 的大作中提到】
: hydrofuel的方法就相当于n arrays merge. 只不过到第k个数就结束了，而且前k-1个
: 数也不用保存。
p*2
38 楼
【在 h*******l 的大作中提到】
: N = 行数
: M = 列数
: k - 第k个
: X = Min(k, NM - k) // k 和 NM - k 的最小值
: Y = Min(N, M) // 行数和列数的最小值
: 复杂度： O( X log(Y))
: ok, 算法如下，假设行数少，k 比 NM - k 小
: 取第一列， 做一个heap， 插入
: ExtractMin() 取出堆里头最小的那个
: 到rowID 取出下一个，插入堆中
c*t
39 楼
可以用一个数组存, arr[rowId] = currID;如果用list,也可以iterator next
【在 p*****2 的大作中提到】
:
:是不是还要存一个currID？这样可以直接取下一个元素。
【在 p*****2 的大作中提到】
:
:
f*4
40 楼
http://zhiqiang.org/blog/science/computer-science/median-algori
这里说的O(K)算法据说很tricky，可惜论文看不到
【在 w****x 的大作中提到】
:
: 恩
这里说的O(K)算法据说很tricky，可惜论文看不到
【在 w****x 的大作中提到】
:
: 恩
f*4
41 楼
堆保存的是(i,j)
题。
【在 l*********8 的大作中提到】
: 我觉得写成n个arrays merge那种heap方便些，不用考虑矩阵元素重复进入heap的问题。
题。
【在 l*********8 的大作中提到】
: 我觉得写成n个arrays merge那种heap方便些，不用考虑矩阵元素重复进入heap的问题。
l*8
42 楼
如果 在heap出(i,j)入(i+1,j)和(i,j+1)，而没有附加检测的话。 在堆里就会出现重
复的(i,j).
【在 f*******4 的大作中提到】
: 堆保存的是(i,j)
:
: 题。
复的(i,j).
【在 f*******4 的大作中提到】
: 堆保存的是(i,j)
:
: 题。
l*8
43 楼
为什么没有人评论我的回答呢？
是好是坏说一下啊。 是不是我表达能力太差，都没有人看？
我觉得在一般情况下，我的方法是好于使用heap的。 比如取中位数，用heap是O(n^2 *
log(n)) time, 我的是O(n* log(n)) time.
【在 l*********8 的大作中提到】
: Given: n by m matrix A,
: k
: 定义
: int low[n]; // low[i]是在第i行查找的下限
: int high[n]; // high[i]是在第i行查找的上限
: low数组初始为全0， high全部是m.
: 取一个pivot (比如第n/2行的第k/n个元素), 在每行的low[i]和high[i]元素范围中找
: 该pivot对应的upper boundary，存为pos[i].
: num = sum( pos[i] - low[i] | for all i) 就是比pivot小的element的数目。
: if (num == k-1) {
是好是坏说一下啊。 是不是我表达能力太差，都没有人看？
我觉得在一般情况下，我的方法是好于使用heap的。 比如取中位数，用heap是O(n^2 *
log(n)) time, 我的是O(n* log(n)) time.
【在 l*********8 的大作中提到】
: Given: n by m matrix A,
: k
: 定义
: int low[n]; // low[i]是在第i行查找的下限
: int high[n]; // high[i]是在第i行查找的上限
: low数组初始为全0， high全部是m.
: 取一个pivot (比如第n/2行的第k/n个元素), 在每行的low[i]和high[i]元素范围中找
: 该pivot对应的upper boundary，存为pos[i].
: num = sum( pos[i] - low[i] | for all i) 就是比pivot小的element的数目。
: if (num == k-1) {
f*e
44 楼
想到了一个Nlog(N)^2的算法。
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
f*e
45 楼
每轮更新是nlog(m)吧？
【在 l*********8 的大作中提到】
: Given: n by m matrix A,
: k
: 定义
: int low[n]; // low[i]是在第i行查找的下限
: int high[n]; // high[i]是在第i行查找的上限
: low数组初始为全0， high全部是m.
: 取一个pivot (比如第n/2行的第k/n个元素), 在每行的low[i]和high[i]元素范围中找
: 该pivot对应的upper boundary，存为pos[i].
: num = sum( pos[i] - low[i] | for all i) 就是比pivot小的element的数目。
: if (num == k-1) {
【在 l*********8 的大作中提到】
: Given: n by m matrix A,
: k
: 定义
: int low[n]; // low[i]是在第i行查找的下限
: int high[n]; // high[i]是在第i行查找的上限
: low数组初始为全0， high全部是m.
: 取一个pivot (比如第n/2行的第k/n个元素), 在每行的low[i]和high[i]元素范围中找
: 该pivot对应的upper boundary，存为pos[i].
: num = sum( pos[i] - low[i] | for all i) 就是比pivot小的element的数目。
: if (num == k-1) {
f*e
46 楼
两年前的advanced algorithm的习题：
告诉大家正确答案吧，我已经figure out该怎么弄了，不知道考试有多难？nnd。
上面有位同学说用求meidan of median,有点像，但不一样。我是用O(N)(第一次建medi
ans的minheap和maxheap，后来为O(log(n))因为只是插入和删除操作)找出median最大
的数组A1和median最小的数组An，然后remove A1的upper half和An的lower half相同
数目的元素(i.e. min(0.5*size(A1),0.5*size(An))。然后重新找最大和最小median，
这么着iterate， so on and so forth. 这样就可以找到所有数组的median。
然后怎么把找kth变成找median呢，方法如下：
如果k!=n/2 or k不是median，就pack几个非常小(比所有数小， if k < n/2 )或非常大
的数(if k > n/2) 平均放到n个数组上去，然后求所有新数组的median，就是求老数组
的kth_element鸟。
这样我们的问题就完美地解决了。
【在 f*****e 的大作中提到】
: 想到了一个Nlog(N)^2的算法。
告诉大家正确答案吧，我已经figure out该怎么弄了，不知道考试有多难？nnd。
上面有位同学说用求meidan of median,有点像，但不一样。我是用O(N)(第一次建medi
ans的minheap和maxheap，后来为O(log(n))因为只是插入和删除操作)找出median最大
的数组A1和median最小的数组An，然后remove A1的upper half和An的lower half相同
数目的元素(i.e. min(0.5*size(A1),0.5*size(An))。然后重新找最大和最小median，
这么着iterate， so on and so forth. 这样就可以找到所有数组的median。
然后怎么把找kth变成找median呢，方法如下：
如果k!=n/2 or k不是median，就pack几个非常小(比所有数小， if k < n/2 )或非常大
的数(if k > n/2) 平均放到n个数组上去，然后求所有新数组的median，就是求老数组
的kth_element鸟。
这样我们的问题就完美地解决了。
【在 f*****e 的大作中提到】
: 想到了一个Nlog(N)^2的算法。
f*e
47 楼
复杂度:
没有，每次pop minheap and maxheap and insert minheap and maxheap操作耗时log(
n)，每次operation，至少有一个数组的size要减半，如果每个数组的size都是n，把一
个数组削的只剩一个要log(n)，然后有n个数组，所以nlogn。nlogn * logn = nlogn^2
medi
目的
常大
的k
【在 f*****e 的大作中提到】
: 两年前的advanced algorithm的习题：
: 告诉大家正确答案吧，我已经figure out该怎么弄了，不知道考试有多难？nnd。
: 上面有位同学说用求meidan of median,有点像，但不一样。我是用O(N)(第一次建medi
: ans的minheap和maxheap，后来为O(log(n))因为只是插入和删除操作)找出median最大
: 的数组A1和median最小的数组An，然后remove A1的upper half和An的lower half相同
: 数目的元素(i.e. min(0.5*size(A1),0.5*size(An))。然后重新找最大和最小median，
: 这么着iterate， so on and so forth. 这样就可以找到所有数组的median。
: 然后怎么把找kth变成找median呢，方法如下：
: 如果k!=n/2 or k不是median，就pack几个非常小(比所有数小， if k < n/2 )或非常大
: 的数(if k > n/2) 平均放到n个数组上去，然后求所有新数组的median，就是求老数组
没有，每次pop minheap and maxheap and insert minheap and maxheap操作耗时log(
n)，每次operation，至少有一个数组的size要减半，如果每个数组的size都是n，把一
个数组削的只剩一个要log(n)，然后有n个数组，所以nlogn。nlogn * logn = nlogn^2
medi
目的
常大
的k
【在 f*****e 的大作中提到】
: 两年前的advanced algorithm的习题：
: 告诉大家正确答案吧，我已经figure out该怎么弄了，不知道考试有多难？nnd。
: 上面有位同学说用求meidan of median,有点像，但不一样。我是用O(N)(第一次建medi
: ans的minheap和maxheap，后来为O(log(n))因为只是插入和删除操作)找出median最大
: 的数组A1和median最小的数组An，然后remove A1的upper half和An的lower half相同
: 数目的元素(i.e. min(0.5*size(A1),0.5*size(An))。然后重新找最大和最小median，
: 这么着iterate， so on and so forth. 这样就可以找到所有数组的median。
: 然后怎么把找kth变成找median呢，方法如下：
: 如果k!=n/2 or k不是median，就pack几个非常小(比所有数小， if k < n/2 )或非常大
: 的数(if k > n/2) 平均放到n个数组上去，然后求所有新数组的median，就是求老数组
b*e
48 楼
这个有问题。或者我没看仔细？
1) 找到 pos[i] worst case 要 O( m * n )
2) 递归中有一步还是 find k'th smallest, 那么岂不是无法递归下去了？
【在 l*********8 的大作中提到】
: Given: n by m matrix A,
: k
: 定义
: int low[n]; // low[i]是在第i行查找的下限
: int high[n]; // high[i]是在第i行查找的上限
: low数组初始为全0， high全部是m.
: 取一个pivot (比如第n/2行的第k/n个元素), 在每行的low[i]和high[i]元素范围中找
: 该pivot对应的upper boundary，存为pos[i].
: num = sum( pos[i] - low[i] | for all i) 就是比pivot小的element的数目。
: if (num == k-1) {
1) 找到 pos[i] worst case 要 O( m * n )
2) 递归中有一步还是 find k'th smallest, 那么岂不是无法递归下去了？
【在 l*********8 的大作中提到】
: Given: n by m matrix A,
: k
: 定义
: int low[n]; // low[i]是在第i行查找的下限
: int high[n]; // high[i]是在第i行查找的上限
: low数组初始为全0， high全部是m.
: 取一个pivot (比如第n/2行的第k/n个元素), 在每行的low[i]和high[i]元素范围中找
: 该pivot对应的upper boundary，存为pos[i].
: num = sum( pos[i] - low[i] | for all i) 就是比pivot小的element的数目。
: if (num == k-1) {
c*t
49 楼
比如说10*10里找第10个数，是不是要插80个最小整数，变成18*10 这样就是找median
(the 90th of 180)?
medi
常大
【在 f*****e 的大作中提到】
: 两年前的advanced algorithm的习题：
: 告诉大家正确答案吧，我已经figure out该怎么弄了，不知道考试有多难？nnd。
: 上面有位同学说用求meidan of median,有点像，但不一样。我是用O(N)(第一次建medi
: ans的minheap和maxheap，后来为O(log(n))因为只是插入和删除操作)找出median最大
: 的数组A1和median最小的数组An，然后remove A1的upper half和An的lower half相同
: 数目的元素(i.e. min(0.5*size(A1),0.5*size(An))。然后重新找最大和最小median，
: 这么着iterate， so on and so forth. 这样就可以找到所有数组的median。
: 然后怎么把找kth变成找median呢，方法如下：
: 如果k!=n/2 or k不是median，就pack几个非常小(比所有数小， if k < n/2 )或非常大
: 的数(if k > n/2) 平均放到n个数组上去，然后求所有新数组的median，就是求老数组
(the 90th of 180)?
medi
常大
【在 f*****e 的大作中提到】
: 两年前的advanced algorithm的习题：
: 告诉大家正确答案吧，我已经figure out该怎么弄了，不知道考试有多难？nnd。
: 上面有位同学说用求meidan of median,有点像，但不一样。我是用O(N)(第一次建medi
: ans的minheap和maxheap，后来为O(log(n))因为只是插入和删除操作)找出median最大
: 的数组A1和median最小的数组An，然后remove A1的upper half和An的lower half相同
: 数目的元素(i.e. min(0.5*size(A1),0.5*size(An))。然后重新找最大和最小median，
: 这么着iterate， so on and so forth. 这样就可以找到所有数组的median。
: 然后怎么把找kth变成找median呢，方法如下：
: 如果k!=n/2 or k不是median，就pack几个非常小(比所有数小， if k < n/2 )或非常大
: 的数(if k > n/2) 平均放到n个数组上去，然后求所有新数组的median，就是求老数组
f*e
50 楼
right!其实也不用真填入，只要知道位置就行了。也不知道还能不能进一步优化。
median
【在 c********t 的大作中提到】
: 比如说10*10里找第10个数，是不是要插80个最小整数，变成18*10 这样就是找median
: (the 90th of 180)?
:
: medi
: 常大
median
【在 c********t 的大作中提到】
: 比如说10*10里找第10个数，是不是要插80个最小整数，变成18*10 这样就是找median
: (the 90th of 180)?
:
: medi
: 常大
c*t
51 楼
不错，和那个link解法一样。当然有论文有O(n)解法，看不到。
这个题还真有在interview碰到的。如果要写codes,我觉得还是 n size heap的解法最
容易实现。
【在 f*****e 的大作中提到】
: right!其实也不用真填入，只要知道位置就行了。也不知道还能不能进一步优化。
:
: median
这个题还真有在interview碰到的。如果要写codes,我觉得还是 n size heap的解法最
容易实现。
【在 f*****e 的大作中提到】
: right!其实也不用真填入，只要知道位置就行了。也不知道还能不能进一步优化。
:
: median
l*8
52 楼
如果在每行使用binary search，那么每轮更新是nlog(m).
但如果采用顺序查找，因为矩阵A在每列也是有序的，所以查找的下标在一轮中是不用
回头的。
例如：
假如pos[4]值为13,因为A[5][13] >= A[4][13]，所以pos[5]就从13开始递减搜索，
假如pos[5]值为8，因为A[6][8] >= A[5][8], 所以pos[6]就从8开始递减搜索。
....
查找下标最多移动m次，重复使用的下标值最多n次，所以是O(n+m).
当然，如果m相对n很大，可以用binary search, 这样nlog(m)的效率还是比 O(n+m)好
些。
【在 f*****e 的大作中提到】
: 每轮更新是nlog(m)吧？
但如果采用顺序查找，因为矩阵A在每列也是有序的，所以查找的下标在一轮中是不用
回头的。
例如：
假如pos[4]值为13,因为A[5][13] >= A[4][13]，所以pos[5]就从13开始递减搜索，
假如pos[5]值为8，因为A[6][8] >= A[5][8], 所以pos[6]就从8开始递减搜索。
....
查找下标最多移动m次，重复使用的下标值最多n次，所以是O(n+m).
当然，如果m相对n很大，可以用binary search, 这样nlog(m)的效率还是比 O(n+m)好
些。
【在 f*****e 的大作中提到】
: 每轮更新是nlog(m)吧？
l*8
53 楼
谢谢你的问题。
1) 见上面对fatalme的回答, 最差情况O(n+m)。
2) 你是说我没有写递归终止条件吗？
递归终止条件就是low和high的boundaries中间只剩下一个元素（或者剩下很少的元
素，然后用简单方法找出第k'个数。）
【在 b*****e 的大作中提到】
: 这个有问题。或者我没看仔细？
: 1) 找到 pos[i] worst case 要 O( m * n )
: 2) 递归中有一步还是 find k'th smallest, 那么岂不是无法递归下去了？
1) 见上面对fatalme的回答, 最差情况O(n+m)。
2) 你是说我没有写递归终止条件吗？
递归终止条件就是low和high的boundaries中间只剩下一个元素（或者剩下很少的元
素，然后用简单方法找出第k'个数。）
【在 b*****e 的大作中提到】
: 这个有问题。或者我没看仔细？
: 1) 找到 pos[i] worst case 要 O( m * n )
: 2) 递归中有一步还是 find k'th smallest, 那么岂不是无法递归下去了？
c*t
54 楼
wwwyhx记得你在别的帖子里揭晓了这个题的最优解，似乎是转化kth变为寻找一个值，
能帮忙找到你的解法吗？
多谢！
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
能帮忙找到你的解法吗？
多谢！
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
w*x
55 楼
那个因该不是最优解，但是想法蛮独特的，是csdn上一个人告诉我的，后来我实现了一
下，很久以前做的。
===============================================================
// Find the kth element in young table
// young table is a two dimensional matrix with its rows and columns sorted
// Solution
// It's hard to find the kth element directly, but its easy to find how many
elements are smaller than a given number.
// So, use binary search to find a number which is bigger than k elements in
the young table. Then, travel through
// the table to the element which is "just" bigger than the given number.
// return the number bigger than
int GetOrder(int** pArr, int n, int m, int v);
int FindKth(int** pArr, int n, int m, int k)
{
assert(pArr && m>0 && n>0 && k>0 && k
int nEnd = pArr[n-1][m-1];
int nK = 0;
int nMid = 0;
int nPrev = -1;
do
{
nMid = (nBeg + nEnd)/2;
nK = GetOrder(pArr, m, n, nMid);
if (nK == nPrev) break;
nPrev = nK;
if (nK < k)
nBeg = nMid;
else
nEnd = nMid;
}
while(nK != k);
int iCur = 0;
int jCur = m-1;
int nRet = 0;
bool bFirst = true;
while (iCur < n && jCur >= 0)
{
if (nMid > pArr[iCur][jCur])
{
if (bFirst)
{
nRet = pArr[iCur][jCur];
bFirst = false;
}
else
nRet = nRet > pArr[iCur][jCur] ? nRet : pArr[iCur][jCur];
iCur++;
}
else
{
jCur--;
}
}
assert(!bFirst);
return nRet;
}
int GetOrder(int** pArr, int m, int n, int v)
{
assert(pArr && m>0 && n>0);
int iCur = 0;
int jCur = m-1;
int nBiggerThan = 0;
while (iCur < n && jCur >= 0)
{
if (pArr[iCur][jCur] >= v)
{
nBiggerThan += n-iCur;
jCur--;
}
else iCur++;
}
return m*n - nBiggerThan;
}
【在 c********t 的大作中提到】
: wwwyhx记得你在别的帖子里揭晓了这个题的最优解，似乎是转化kth变为寻找一个值，
: 能帮忙找到你的解法吗？
: 多谢！
c*t
56 楼
多谢！
sorted
many
in
【在 w****x 的大作中提到】
:
: 那个因该不是最优解，但是想法蛮独特的，是csdn上一个人告诉我的，后来我实现了一
: 下，很久以前做的。
: ===============================================================
: // Find the kth element in young table
: // young table is a two dimensional matrix with its rows and columns sorted
: // Solution
: // It's hard to find the kth element directly, but its easy to find how many
: elements are smaller than a given number.
: // So, use binary search to find a number which is bigger than k elements in
sorted
many
in
【在 w****x 的大作中提到】
:
: 那个因该不是最优解，但是想法蛮独特的，是csdn上一个人告诉我的，后来我实现了一
: 下，很久以前做的。
: ===============================================================
: // Find the kth element in young table
: // young table is a two dimensional matrix with its rows and columns sorted
: // Solution
: // It's hard to find the kth element directly, but its easy to find how many
: elements are smaller than a given number.
: // So, use binary search to find a number which is bigger than k elements in
l*8
57 楼
不错，很有意思的解法
不过， if (nK == nPrev) break; 有问题吧？
sorted
many
in
【在 w****x 的大作中提到】
:
: 那个因该不是最优解，但是想法蛮独特的，是csdn上一个人告诉我的，后来我实现了一
: 下，很久以前做的。
: ===============================================================
: // Find the kth element in young table
: // young table is a two dimensional matrix with its rows and columns sorted
: // Solution
: // It's hard to find the kth element directly, but its easy to find how many
: elements are smaller than a given number.
: // So, use binary search to find a number which is bigger than k elements in
不过， if (nK == nPrev) break; 有问题吧？
sorted
many
in
【在 w****x 的大作中提到】
:
: 那个因该不是最优解，但是想法蛮独特的，是csdn上一个人告诉我的，后来我实现了一
: 下，很久以前做的。
: ===============================================================
: // Find the kth element in young table
: // young table is a two dimensional matrix with its rows and columns sorted
: // Solution
: // It's hard to find the kth element directly, but its easy to find how many
: elements are smaller than a given number.
: // So, use binary search to find a number which is bigger than k elements in
c*t
58 楼
这个解法很牛。和你的解法复杂度一样 （m+n)*lg(m*n)
但是充分利用了杨氏矩阵search容易O(m+n)的特点,代码好写很多。
if (nK == nPrev) break;这句感觉是有些问题。什么时候会产生？这时候nK != K,
后面找nk不就错了？
【在 l*********8 的大作中提到】
: 不错，很有意思的解法
: 不过， if (nK == nPrev) break; 有问题吧？
:
: sorted
: many
: in
但是充分利用了杨氏矩阵search容易O(m+n)的特点,代码好写很多。
if (nK == nPrev) break;这句感觉是有些问题。什么时候会产生？这时候nK != K,
后面找nk不就错了？
【在 l*********8 的大作中提到】
: 不错，很有意思的解法
: 不过， if (nK == nPrev) break; 有问题吧？
:
: sorted
: many
: in
l*8
59 楼
是的，我的方法顶多比这个方法快个常数级，但写起来比较麻烦。
-----
nK == nPrev的一个例子：
1 2 3 4
2 3 4 5
3 4 5 100000
一开始nMid是50000，只有一个数字比nMid大。
然后nMid是25000, 还是只有一个数字比nMid大。
这个时候，nK == nPrev， 循环非正常结束了。
【在 c********t 的大作中提到】
: 这个解法很牛。和你的解法复杂度一样 （m+n)*lg(m*n)
: 但是充分利用了杨氏矩阵search容易O(m+n)的特点,代码好写很多。
: if (nK == nPrev) break;这句感觉是有些问题。什么时候会产生？这时候nK != K,
: 后面找nk不就错了？
-----
nK == nPrev的一个例子：
1 2 3 4
2 3 4 5
3 4 5 100000
一开始nMid是50000，只有一个数字比nMid大。
然后nMid是25000, 还是只有一个数字比nMid大。
这个时候，nK == nPrev， 循环非正常结束了。
【在 c********t 的大作中提到】
: 这个解法很牛。和你的解法复杂度一样 （m+n)*lg(m*n)
: 但是充分利用了杨氏矩阵search容易O(m+n)的特点,代码好写很多。
: if (nK == nPrev) break;这句感觉是有些问题。什么时候会产生？这时候nK != K,
: 后面找nk不就错了？
j*y
60 楼
你这个复杂度其实很高的，比如 k = NM / 2.
而且也没有利用到 Young table的性质。
【在 h*******l 的大作中提到】
: N = 行数
: M = 列数
: k - 第k个
: X = Min(k, NM - k) // k 和 NM - k 的最小值
: Y = Min(N, M) // 行数和列数的最小值
: 复杂度： O( X log(Y))
: ok, 算法如下，假设行数少，k 比 NM - k 小
: 取第一列， 做一个heap， 插入 , 即 数值 和 哪一行的数值
: ExtractMin() 取出堆里头最小的那个
: 到rowID 取出下一个，插入堆中
而且也没有利用到 Young table的性质。
【在 h*******l 的大作中提到】
: N = 行数
: M = 列数
: k - 第k个
: X = Min(k, NM - k) // k 和 NM - k 的最小值
: Y = Min(N, M) // 行数和列数的最小值
: 复杂度： O( X log(Y))
: ok, 算法如下，假设行数少，k 比 NM - k 小
: 取第一列， 做一个heap， 插入
: ExtractMin() 取出堆里头最小的那个
: 到rowID 取出下一个，插入堆中
相关阅读
阿里HR是鄙人见过湾区最大牌的在大农村怎么解决吃海鲜的问题有没有it公司找兼职的？有在guidewire的兄弟姐妹么？突破mitbbs十字限制 随机签名档userscript板上喊刷题的那帮人可以停一下了机器人的刷题水平如何我发现一小撮人的思路很奇怪啊我给大家讲道题吧。leetcode题目视频讲解HP Enterprise砍掉5000人Did anyone use interview training/coaching service?刷题最后都是刷筛选出来短视的傻逼面试的时候理解错题意了，面试官一般会点出来吗？锁男爆公司首字母，只是想拿回路费，不是诚心警告后来人亚麻 Sr SDE 岗位面试的问题如果不考虑大苞谷 刷题和打农药你觉得哪个有意义？十年河东，十年河西除了Google还有哪家不问system design啊OPT收到时间是怎么解释？