一道Google面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道Google面试题

一道Google面试题# JobHunting - 待字闺中

c*e2011-01-29 08:01

1 楼

Given a N*N Matrix. All rows are sorted, and all columns are sorted. Find
the
Kth Largest element of the matrix.

z*o2011-01-29 08:01

2 楼

怎么这个题重现率这么高啊......
我只能做 kLog(n) 或者 nLog(Value_Range)的。

f*42011-01-29 08:01

3 楼

能展开讲讲么？

【在 z****o 的大作中提到】

: 怎么这个题重现率这么高啊......
: 我只能做 kLog(n) 或者 nLog(Value_Range)的。

h*c2011-01-29 08:01

4 楼

有row hash 和 column hash码？

【在 c****e 的大作中提到】

: Given a N*N Matrix. All rows are sorted, and all columns are sorted. Find
: the
: Kth Largest element of the matrix.

l*a2011-01-29 08:01

5 楼

升序还是降序排列？
用priority queue。

f*42011-01-29 08:01

6 楼

杨氏矩阵本身不就是一个heap么

【在 l*****a 的大作中提到】

: 升序还是降序排列？
: 用priority queue。

c*n2011-01-29 08:01

7 楼

young试tableau
same algo as heapify

【在 c****e 的大作中提到】

: Given a N*N Matrix. All rows are sorted, and all columns are sorted. Find
: the
: Kth Largest element of the matrix.

l*a2011-01-29 08:01

8 楼

好吧，我假设的是原杨氏矩阵不能够被修改。
能修改的话，如ls说的就可以了。

【在 f*******4 的大作中提到】

: 杨氏矩阵本身不就是一个heap么

s*t2011-01-29 08:01

9 楼

我能想到的是这样：
每行取最大O(n), 是一个sorted array，取最大O(1), 然后 insert next value to t
he right place O(log(n)). k个所以klog(n). 是这个意思吗？
有人说用heap，但是感觉建个heap就要nlog(n)吧。

【在 z****o 的大作中提到】

: 怎么这个题重现率这么高啊......
: 我只能做 kLog(n) 或者 nLog(Value_Range)的。