w****x
发帖数: 2483 | 1 Given an array with all elements sorted on each individual row and column
find the K-th smallest one
有个做法是用heap, 但好像也不是很合适... |
f*****e
发帖数: 2992 | 2 复杂度要求呢？
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
|
C***U
发帖数: 2406 | 3 你是说给定一个matrix 是么?
【在 w****x 的大作中提到】
: Given an array with all elements sorted on each individual row and column
: find the K-th smallest one
: 有个做法是用heap, 但好像也不是很合适...
|
l****c
发帖数: 782 | 4 我怎么觉得用heap挺好的呢，worst case n^2, 但一般用不到那么多吧 |
c*****r
发帖数: 214 | 5 复杂度klogk， worst case是 n^2 log n, 跟直接sort是一样的
【在 l****c 的大作中提到】
: 我怎么觉得用heap挺好的呢，worst case n^2, 但一般用不到那么多吧
|
l*********8
发帖数: 4642 | 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, 但好像也不是很合适...
|
l****c
发帖数: 782 | 7 大哥，直接sort和k无关，heap至少还用的k吧
【在 c*****r 的大作中提到】
: 复杂度klogk， worst case是 n^2 log n, 跟直接sort是一样的
|
C***U
发帖数: 2406 | 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
|
c*****r
发帖数: 214 | 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吧
|
l****c
发帖数: 782 | 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****c
发帖数: 782 | 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吧
|
l*********8
发帖数: 4642 | 12 哦，是finad the kth smallest one.
thanks!
【在 C***U 的大作中提到】
: 你应该把题目再看一边
|
l*********8
发帖数: 4642 | 13 恩，看错了。 楼主是要在matrix里find the K-th smallest one
【在 l****c 的大作中提到】
: 这个是在matrix找数
|
e***s
发帖数: 799 | 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****c
发帖数: 782 | |
K*********n
发帖数: 2852 | 16 我觉得实现不太可能吧，percolate up和percolate down什么的。直接用没什么的。
当然实现其实也不难，我觉得应该是需要掌握的内容。
【在 l****c 的大作中提到】
: 话说，面试会让写heap代码不？
|
l****c
发帖数: 782 | 17 嗯，原理不难，就是怕要是让现场写，没写过的话，像我这种档次的估计会崩溃了。
【在 K*********n 的大作中提到】
: 我觉得实现不太可能吧，percolate up和percolate down什么的。直接用没什么的。
: 当然实现其实也不难，我觉得应该是需要掌握的内容。
|
K*********n
发帖数: 2852 | 18 基本数据结构实现一遍，两天够了
【在 l****c 的大作中提到】
: 嗯，原理不难，就是怕要是让现场写，没写过的话，像我这种档次的估计会崩溃了。
|
d*********g
发帖数: 154 | |
l*********8
发帖数: 4642 | 20 k = 1/2 * n^2的时候（中位数）。 O(k^2) 就是O(n^4).
【在 d*********g 的大作中提到】
: 用heap可以做到O(k^2)吧~
|
|
|
w****x
发帖数: 2483 | |
l*********8
发帖数: 4642 | 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, 但好像也不是很合适...
|
l*********8
发帖数: 4642 | 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) {
|
d*s
发帖数: 699 | 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)个，得到结果 |
l*********8
发帖数: 4642 | 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)个，得到结果
|
d*s
发帖数: 699 | 26 确实理解有问题
【在 l*********8 的大作中提到】
: 可能是这样的矩阵：
: 1 6 10
: 2 8 11
: 6 9 12
: 照/分层不总是成立。
|
h*******l
发帖数: 22 | 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(行数)) 的复杂度已经差不多够低的了 |
f*******4
发帖数: 64 | 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
发帖数: 2483 | 29
恩
【在 f*******4 的大作中提到】
: heap做法指的是出(i,j)入(i+1,j)和(i,j+1)？
|
l*********8
发帖数: 4642 | 30 怎样保证元素不重复入heap?
【在 w****x 的大作中提到】
:
: 恩
|
|
|
c********t
发帖数: 5706 | 31 感觉需要一个structure, 除了value 还需要 i, j
heap顺序只比较value，入的时候还要判断i,j,去掉重复插入。还真的需要写一个
customized heap啊。
【在 l*********8 的大作中提到】
: 怎样保证元素不重复入heap?
|
l*********8
发帖数: 4642 | 32 我觉得写成n个arrays merge那种heap方便些，不用考虑矩阵元素重复进入heap的问题。
【在 c********t 的大作中提到】
: 感觉需要一个structure, 除了value 还需要 i, j
: heap顺序只比较value，入的时候还要判断i,j,去掉重复插入。还真的需要写一个
: customized heap啊。
|
c********t
发帖数: 5706 | 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 取出下一个，插入堆中
|
c********t
发帖数: 5706 | 34 n个arrays merge的heap, 和一个数一个数插入heap复杂度是不是一样啊？
既然排好序的，直接merge 也是O(n*m)
题。
【在 l*********8 的大作中提到】
: 我觉得写成n个arrays merge那种heap方便些，不用考虑矩阵元素重复进入heap的问题。
|
g**e
发帖数: 6127 | 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, 但好像也不是很合适...
|
l*********8
发帖数: 4642 | 36 hydrofuel的方法就相当于n arrays merge. 只不过到第k个数就结束了，而且前k-1个
数也不用保存。
【在 c********t 的大作中提到】
: n个arrays merge的heap, 和一个数一个数插入heap复杂度是不是一样啊？
: 既然排好序的，直接merge 也是O(n*m)
:
: 题。
|
c********t
发帖数: 5706 | 37 是的，明白你的意思了。
【在 l*********8 的大作中提到】
: hydrofuel的方法就相当于n arrays merge. 只不过到第k个数就结束了，而且前k-1个
: 数也不用保存。
|
p*****2
发帖数: 21240 | 38
是不是还要存一个currID？这样可以直接取下一个元素。
【在 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
发帖数: 5706 | 39 可以用一个数组存, arr[rowId] = currID;如果用list,也可以iterator next
【在 p*****2 的大作中提到】
:
: 是不是还要存一个currID？这样可以直接取下一个元素。
|
f*******4
发帖数: 64 | |
|
|
f*******4
发帖数: 64 | 41 堆保存的是(i,j)
题。
【在 l*********8 的大作中提到】
: 我觉得写成n个arrays merge那种heap方便些，不用考虑矩阵元素重复进入heap的问题。
|
l*********8
发帖数: 4642 | 42 如果 在heap出(i,j)入(i+1,j)和(i,j+1)，而没有附加检测的话。 在堆里就会出现重
复的(i,j).
【在 f*******4 的大作中提到】
: 堆保存的是(i,j)
:
: 题。
|
l*********8
发帖数: 4642 | 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) {
|
f*****e
发帖数: 2992 | 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, 但好像也不是很合适...
|
f*****e
发帖数: 2992 | 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) {
|
f*****e
发帖数: 2992 | 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的算法。
|
f*****e
发帖数: 2992 | 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，就是求老数组
|
b*****e
发帖数: 474 | 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) {
|
c********t
发帖数: 5706 | 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，就是求老数组
|
f*****e
发帖数: 2992 | 50 right!其实也不用真填入，只要知道位置就行了。也不知道还能不能进一步优化。
median
【在 c********t 的大作中提到】
: 比如说10*10里找第10个数，是不是要插80个最小整数，变成18*10 这样就是找median
: (the 90th of 180)?
:
: medi
: 常大
|
|
|
c********t
发帖数: 5706 | 51 不错，和那个link解法一样。当然有论文有O(n)解法，看不到。
这个题还真有在interview碰到的。如果要写codes,我觉得还是 n size heap的解法最
容易实现。
【在 f*****e 的大作中提到】
: right!其实也不用真填入，只要知道位置就行了。也不知道还能不能进一步优化。
:
: median
|
l*********8
发帖数: 4642 | 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)吧？
|
l*********8
发帖数: 4642 | 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, 那么岂不是无法递归下去了？
|
c********t
发帖数: 5706 | 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
发帖数: 2483 | 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 nBeg = pArr[0][0];
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
发帖数: 5706 | 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
|
l*********8
发帖数: 4642 | 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
|
c********t
发帖数: 5706 | 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
|
l*********8
发帖数: 4642 | 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不就错了？
|
j*****y
发帖数: 1071 | 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 取出下一个，插入堆中
|
