由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 发个一直没有见过满意答案的题吧
相关主题
An interview question of finding the median in a moving window.问个design的问题
又想起一道google题目Top K in N sorted array
问大家一个cpp中function pointer的问题问一道题(9)
Two-Sigma面经G家电面的两个题
问个题sliding windows中维持topk频繁的query
G家电面题目LinkedIn面经(已跪),攒个rp
问两道google题刚电面完l家,只敲了一道题,看来是挂了。。。
讨论一道题面试用C++, heap 怎么办?
相关话题的讨论汇总
话题: int话题: parr话题: icur话题: jcur话题: heap
进入JobHunting版参与讨论
1 (共1页)
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

相关主题
G家电面题目问个design的问题
问两道google题Top K in N sorted array
讨论一道题问一道题(9)
进入JobHunting版参与讨论
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
15
话说,面试会让写heap代码不?
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
19
用heap可以做到O(k^2)吧~
l*********8
发帖数: 4642
20
k = 1/2 * n^2的时候(中位数)。 O(k^2) 就是O(n^4).

【在 d*********g 的大作中提到】
: 用heap可以做到O(k^2)吧~
相关主题
G家电面的两个题刚电面完l家,只敲了一道题,看来是挂了。。。
sliding windows中维持topk频繁的query面试用C++, heap 怎么办?
LinkedIn面经(已跪),攒个rpG电面的一个题
进入JobHunting版参与讨论
w****x
发帖数: 2483
21
表示还没看到满意答案, 呼唤two爷~~~~
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 的大作中提到】
:
: 恩

相关主题
攒人品,twitter电话面经又想起一道google题目
请教MinHeap用STL实现问大家一个cpp中function pointer的问题
An interview question of finding the median in a moving window.Two-Sigma面经
进入JobHunting版参与讨论
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
40
http://zhiqiang.org/blog/science/computer-science/median-algori
这里说的O(K)算法据说很tricky,可惜论文看不到

【在 w****x 的大作中提到】
:
: 恩

相关主题
Two-Sigma面经问两道google题
问个题讨论一道题
G家电面题目问个design的问题
进入JobHunting版参与讨论
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
: 常大

相关主题
Top K in N sorted arraysliding windows中维持topk频繁的query
问一道题(9)LinkedIn面经(已跪),攒个rp
G家电面的两个题刚电面完l家,只敲了一道题,看来是挂了。。。
进入JobHunting版参与讨论
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 取出下一个,插入堆中

1 (共1页)
进入JobHunting版参与讨论
相关主题
面试用C++, heap 怎么办?问个题
G电面的一个题G家电面题目
攒人品,twitter电话面经问两道google题
请教MinHeap用STL实现讨论一道题
An interview question of finding the median in a moving window.问个design的问题
又想起一道google题目Top K in N sorted array
问大家一个cpp中function pointer的问题问一道题(9)
Two-Sigma面经G家电面的两个题
相关话题的讨论汇总
话题: int话题: parr话题: icur话题: jcur话题: heap