由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - find kth element in n*n sorted matrix
相关主题
~~问两道AMAZON电面题有A[i]
请教一道careercup 150上的题问一道老题
大牛们看看这题:Find Peak Element IImatrix question
一道热门的 Google 面试题Amazon algorithm question, google
Print out all elements in a sorted matrix求分析这题的时间复杂度
刚看到的一道google面试题求教矩阵改零的问题 (转载)
一个小公司面经question about MATLAB matrix squaring (转载)
算法问题,m*m matrixMaximal Rectangle如果不要求是Rectangle就要简单得多
相关话题的讨论汇总
话题: int话题: node话题: mid话题: matrix话题: val
1 (共1页)
b*****c
发帖数: 1103
1
sorted matrix = each row/column is sorted
remember k=O(n^2)
write code to solve in n*lg n
----------------------
O(n^2) is simple and stupid --- QuickSelect
b*****c
发帖数: 1103
2
O(n) is doable. But I need O(n lgn) and the code.
O(n) algorithm
http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf
T*******e
发帖数: 4928
3
啊,最近面世我刚遇到这题。一个印度面世官出的, 你不会和我面得同一家吧?
cupertino的.
s******u
发帖数: 550
4
mark,觉得这个题目很有趣,有时间做做
l******a
发帖数: 14
5
Divid the matrix to 2 by 2. Each are n/2 X n/2
If k<=n*n/4, restrain search to only the top left square
Else if k =>n*n*3/4 restrain search to only the right bottom square
Else restrain search to top right and bottom left square
This way you cut it at least to half size each time
T(n) = 2T(n/2) O(1)
So T(n) = O(nlogn)

O(n) is doable. But I need O(n lgn) and the code.O(n) algorithmhttp://www.cse.yorku.ca/~........

【在 b*****c 的大作中提到】
: O(n) is doable. But I need O(n lgn) and the code.
: O(n) algorithm
: http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf

T*******e
发帖数: 4928
6
Are you sure it's working? For example,
Find the 4th element in 6x6 matrix.
matrix:
1 20 30 40 50 60
2 21 31 41 51 61
3 22 32 42 52 62
4 23 33 43 53 63
5 24 34 44 54 64
6 25 35 45 55 65

【在 l******a 的大作中提到】
: Divid the matrix to 2 by 2. Each are n/2 X n/2
: If k<=n*n/4, restrain search to only the top left square
: Else if k =>n*n*3/4 restrain search to only the right bottom square
: Else restrain search to top right and bottom left square
: This way you cut it at least to half size each time
: T(n) = 2T(n/2) O(1)
: So T(n) = O(nlogn)
:
: O(n) is doable. But I need O(n lgn) and the code.O(n) algorithmhttp://www.cse.yorku.ca/~........

b*****c
发帖数: 1103
7
樓上的,
1 1 1 1
1 2 2 2
1 2 2 2
1 2 2 2
找k=4,你的算法錯了,不能只看topleft
b*****c
发帖数: 1103
8
1) O(k*log(min(k,n)) , just look at my original thread, k=O(n^2) !!!!
Quickselect = O(n^2). O(k*log(min(k,n)) will be "Stupider"
2) O((n+n)*log(range of values in matrix)
tell me how do you solve
1 2 3 99999
1 2 3 99999
1 2 3 99999
1 2 3 99999
k=5

of
the

【在 T*******e 的大作中提到】
: Are you sure it's working? For example,
: Find the 4th element in 6x6 matrix.
: matrix:
: 1 20 30 40 50 60
: 2 21 31 41 51 61
: 3 22 32 42 52 62
: 4 23 33 43 53 63
: 5 24 34 44 54 64
: 6 25 35 45 55 65

T*******e
发帖数: 4928
9
I didn't say they were better than O(n^2). I just say they
are two methods that I can think of.
l******a
发帖数: 14
10
Here is another try:
Sp=0;
Ep=n-1;
While (sp {
mid=(sp ep)/2;
Pick m[mid][mid],
walk up and right to find last column index on each row( above row mid) that
is less than m[mid][mid]
Then walk down and left to find last column index on each row( below row mid
) that is less than m[mid][mid]
Now you have separate the whole data set to 2 data set in 2n time
If first set count>k, ep=mid;
Else{ sp= mid 1;k-=count of set 1;}
}
So loop logn time! you will find the final mid associate with 2n elements,
you can find the kth element from these 2n element
相关主题
刚看到的一道google面试题有A[i]
一个小公司面经问一道老题
算法问题,m*m matrixmatrix question
b*****c
发帖数: 1103
11
good job. running simulation to verify

that
mid

【在 l******a 的大作中提到】
: Here is another try:
: Sp=0;
: Ep=n-1;
: While (sp: {
: mid=(sp ep)/2;
: Pick m[mid][mid],
: walk up and right to find last column index on each row( above row mid) that
: is less than m[mid][mid]
: Then walk down and left to find last column index on each row( below row mid

b*****c
发帖数: 1103
12
lol.
1 2 4
2 3 4
2 4 4
k=5就错了

【在 s******u 的大作中提到】
: mark,觉得这个题目很有趣,有时间做做
s********k
发帖数: 2352
13
kth element难道不是matrix[k/n][k%n-1]?
b*****c
发帖数: 1103
14
是每行每列分别有序,不是将matrix视作array的有序,
前者是sorted matrix的数学定义,后者是不知出处的定义

【在 s********k 的大作中提到】
: kth element难道不是matrix[k/n][k%n-1]?
s********k
发帖数: 2352
15
找 kth 最小 element?

【在 b*****c 的大作中提到】
: 是每行每列分别有序,不是将matrix视作array的有序,
: 前者是sorted matrix的数学定义,后者是不知出处的定义

b*****c
发帖数: 1103
16
不过最小是不表意的,因为kth最小和kth最大两种说法是同一意思。

【在 s********k 的大作中提到】
: 找 kth 最小 element?
T*******e
发帖数: 4928
17

you can verify it yourself or just lol. What do I care.

【在 b*****c 的大作中提到】
: 不过最小是不表意的,因为kth最小和kth最大两种说法是同一意思。
b*****c
发帖数: 1103
18
是看不懂你的过程,叫你用这个简单例子讲

【在 T*******e 的大作中提到】
:
: you can verify it yourself or just lol. What do I care.

b*****c
发帖数: 1103
19
bump
D*********d
发帖数: 125
20
每次把矩阵划成4份,每次至少能够扔掉1/4,也就是说如果k>左上角的最大值,那么扔
掉左上角,如果k<右下角的最小值,那么扔掉右下角,这样不知道是不是
T(n) = 3*T(1/4n)+a?然后复杂度是多少?有点蒙。。
相关主题
Amazon algorithm question, googlequestion about MATLAB matrix squaring (转载)
求分析这题的时间复杂度Maximal Rectangle如果不要求是Rectangle就要简单得多
求教矩阵改零的问题 (转载)问一道算法题
j********8
发帖数: 10
21
//Best first search, time complexity O(klog(n)). The size of heap is at most
2*n. Every time an element is popped from the heap or inserted to the heap,
O(log(n)). We need to do the pop and insert operations k times. So the time
complexity is O(klog(n)).
//Space complexity O(n), because there are at most 2*n nodes in the priority
queue.
struct node
{
int index;
int val;
node(int index_, int val_): index(index_), val(val_){}
bool operator > (const node& other) const
{
return val > other.val;
}
};
static int findKthSmallest2D(const vector> &mat, int k)
{
int res = INT_MIN;
int m = mat.size();
if (m == 0)
{
return res;
}
int n = mat[0].size();
if (n == 0)
{
return res;
}
priority_queue, greater> minHeap;
unordered_set hash; // to avoid duplication.
minHeap.push(node(0, mat[0][0]));
hash.insert(0);
while (!minHeap.empty())
{
node top = minHeap.top();
minHeap.pop();
k--;
if (k == 0)
{
return top.val;
}
int i = top.index / n;
int j = top.index % n;
int c1 = (i + 1) * n + j;
int c2 = i * n + j + 1;
if (i + 1 < m && hash.find(c1) == hash.end())
{
minHeap.push(node(c1, mat[i + 1][j]));
hash.insert(c1);
}
if (j + 1 < n && hash.find(c2) == hash.end())
{
minHeap.push(node(c2, mat[i][j + 1]));
hash.insert(c2);
}
}
return res;
}
W*********y
发帖数: 481
22
从右上开始找,
若大于input,move down
若小于input,move left,
若等于input, return
一直找到左壁或者下壁。ruturn false.
这样扫 2*n个元素必能找到,
b******g
发帖数: 3616
23
哪里有input?.....这是看成leetcode上那道了?....

【在 W*********y 的大作中提到】
: 从右上开始找,
: 若大于input,move down
: 若小于input,move left,
: 若等于input, return
: 一直找到左壁或者下壁。ruturn false.
: 这样扫 2*n个元素必能找到,

j*******t
发帖数: 223
b*****c
发帖数: 1103
25
sorted matrix = each row/column is sorted
e.g.,
1 6 6
2 7 7
2 8 9
k=7
remember k=O(n^2)
write code to solve in n*lg n
----------------------
O(n^2) is simple and stupid --- QuickSelect!!!!!!!!
b*****c
发帖数: 1103
26
O(n) is doable. But I need O(n lgn) and the code.
O(n) algorithm
http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf
T*******e
发帖数: 4928
27
啊,最近面世我刚遇到这题。一个印度面世官出的, 你不会和我面得同一家吧?
cupertino的.
s******u
发帖数: 550
28
mark,觉得这个题目很有趣,有时间做做
l******a
发帖数: 14
29
Divid the matrix to 2 by 2. Each are n/2 X n/2
If k<=n*n/4, restrain search to only the top left square
Else if k =>n*n*3/4 restrain search to only the right bottom square
Else restrain search to top right and bottom left square
This way you cut it at least to half size each time
T(n) = 2T(n/2) O(1)
So T(n) = O(nlogn)

O(n) is doable. But I need O(n lgn) and the code.O(n) algorithmhttp://www.cse.yorku.ca/~........

【在 b*****c 的大作中提到】
: O(n) is doable. But I need O(n lgn) and the code.
: O(n) algorithm
: http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf

T*******e
发帖数: 4928
30
Are you sure it's working? For example,
Find the 4th element in 6x6 matrix.
matrix:
1 20 30 40 50 60
2 21 31 41 51 61
3 22 32 42 52 62
4 23 33 43 53 63
5 24 34 44 54 64
6 25 35 45 55 65

【在 l******a 的大作中提到】
: Divid the matrix to 2 by 2. Each are n/2 X n/2
: If k<=n*n/4, restrain search to only the top left square
: Else if k =>n*n*3/4 restrain search to only the right bottom square
: Else restrain search to top right and bottom left square
: This way you cut it at least to half size each time
: T(n) = 2T(n/2) O(1)
: So T(n) = O(nlogn)
:
: O(n) is doable. But I need O(n lgn) and the code.O(n) algorithmhttp://www.cse.yorku.ca/~........

相关主题
再来道题请教一道careercup 150上的题
请教2个 huge file的面试题大牛们看看这题:Find Peak Element II
~~问两道AMAZON电面题一道热门的 Google 面试题
b*****c
发帖数: 1103
31
樓上的,
1 1 1 1
1 2 2 2
1 2 2 2
1 2 2 2
找k=4,你的算法錯了,不能只看topleft
b*****c
发帖数: 1103
32
1) O(k*log(min(k,n)) , just look at my original thread, k=O(n^2) !!!!
Quickselect = O(n^2). O(k*log(min(k,n)) will be "Stupider"
2) O((n+n)*log(range of values in matrix)
tell me how do you solve
1 2 3 99999
1 2 3 99999
1 2 3 99999
1 2 3 99999
k=5

of
the

【在 T*******e 的大作中提到】
: Are you sure it's working? For example,
: Find the 4th element in 6x6 matrix.
: matrix:
: 1 20 30 40 50 60
: 2 21 31 41 51 61
: 3 22 32 42 52 62
: 4 23 33 43 53 63
: 5 24 34 44 54 64
: 6 25 35 45 55 65

T*******e
发帖数: 4928
33
I didn't say they were better than O(n^2). I just say they
are two methods that I can think of.
l******a
发帖数: 14
34
Here is another try:
Sp=0;
Ep=n-1;
While (sp {
mid=(sp ep)/2;
Pick m[mid][mid],
walk up and right to find last column index on each row( above row mid) that
is less than m[mid][mid]
Then walk down and left to find last column index on each row( below row mid
) that is less than m[mid][mid]
Now you have separate the whole data set to 2 data set in 2n time
If first set count>k, ep=mid;
Else{ sp= mid 1;k-=count of set 1;}
}
So loop logn time! you will find the final mid associate with 2n elements,
you can find the kth element from these 2n element
b*****c
发帖数: 1103
35
good job. running simulation to verify

that
mid

【在 l******a 的大作中提到】
: Here is another try:
: Sp=0;
: Ep=n-1;
: While (sp: {
: mid=(sp ep)/2;
: Pick m[mid][mid],
: walk up and right to find last column index on each row( above row mid) that
: is less than m[mid][mid]
: Then walk down and left to find last column index on each row( below row mid

b*****c
发帖数: 1103
36
lol.
1 2 4
2 3 4
2 4 4
k=5就错了

【在 s******u 的大作中提到】
: mark,觉得这个题目很有趣,有时间做做
s********k
发帖数: 2352
37
kth element难道不是matrix[k/n][k%n-1]?
b*****c
发帖数: 1103
38
是每行每列分别有序,不是将matrix视作array的有序,
前者是sorted matrix的数学定义,后者是不知出处的定义

【在 s********k 的大作中提到】
: kth element难道不是matrix[k/n][k%n-1]?
s********k
发帖数: 2352
39
找 kth 最小 element?

【在 b*****c 的大作中提到】
: 是每行每列分别有序,不是将matrix视作array的有序,
: 前者是sorted matrix的数学定义,后者是不知出处的定义

b*****c
发帖数: 1103
40
不过最小是不表意的,因为kth最小和kth最大两种说法是同一意思。

【在 s********k 的大作中提到】
: 找 kth 最小 element?
相关主题
一道热门的 Google 面试题一个小公司面经
Print out all elements in a sorted matrix算法问题,m*m matrix
刚看到的一道google面试题有A[i]
T*******e
发帖数: 4928
41

you can verify it yourself or just lol. What do I care.

【在 b*****c 的大作中提到】
: 不过最小是不表意的,因为kth最小和kth最大两种说法是同一意思。
b*****c
发帖数: 1103
42
是看不懂你的过程,叫你用这个简单例子讲

【在 T*******e 的大作中提到】
:
: you can verify it yourself or just lol. What do I care.

b*****c
发帖数: 1103
43
bump
D*********d
发帖数: 125
44
每次把矩阵划成4份,每次至少能够扔掉1/4,也就是说如果k>左上角的最大值,那么扔
掉左上角,如果k<右下角的最小值,那么扔掉右下角,这样不知道是不是
T(n) = 3*T(1/4n)+a?然后复杂度是多少?有点蒙。。
j********8
发帖数: 10
45
//Best first search, time complexity O(klog(n)). The size of heap is at most
2*n. Every time an element is popped from the heap or inserted to the heap,
O(log(n)). We need to do the pop and insert operations k times. So the time
complexity is O(klog(n)).
//Space complexity O(n), because there are at most 2*n nodes in the priority
queue.
struct node
{
int index;
int val;
node(int index_, int val_): index(index_), val(val_){}
bool operator > (const node& other) const
{
return val > other.val;
}
};
static int findKthSmallest2D(const vector> &mat, int k)
{
int res = INT_MIN;
int m = mat.size();
if (m == 0)
{
return res;
}
int n = mat[0].size();
if (n == 0)
{
return res;
}
priority_queue, greater> minHeap;
unordered_set hash; // to avoid duplication.
minHeap.push(node(0, mat[0][0]));
hash.insert(0);
while (!minHeap.empty())
{
node top = minHeap.top();
minHeap.pop();
k--;
if (k == 0)
{
return top.val;
}
int i = top.index / n;
int j = top.index % n;
int c1 = (i + 1) * n + j;
int c2 = i * n + j + 1;
if (i + 1 < m && hash.find(c1) == hash.end())
{
minHeap.push(node(c1, mat[i + 1][j]));
hash.insert(c1);
}
if (j + 1 < n && hash.find(c2) == hash.end())
{
minHeap.push(node(c2, mat[i][j + 1]));
hash.insert(c2);
}
}
return res;
}
W*********y
发帖数: 481
46
从右上开始找,
若大于input,move down
若小于input,move left,
若等于input, return
一直找到左壁或者下壁。ruturn false.
这样扫 2*n个元素必能找到,
b******g
发帖数: 3616
47
哪里有input?.....这是看成leetcode上那道了?....

【在 W*********y 的大作中提到】
: 从右上开始找,
: 若大于input,move down
: 若小于input,move left,
: 若等于input, return
: 一直找到左壁或者下壁。ruturn false.
: 这样扫 2*n个元素必能找到,

j*******t
发帖数: 223
b*****c
发帖数: 1103
49
不是说了k=o(n^2)吗,晕死
o(n*lgn)基本没戏了,看能不能数学证明下这是不可能的
h*********r
发帖数: 76
50
请问能不能说明下quick select怎么做这题?多谢

【在 b*****c 的大作中提到】
: 不是说了k=o(n^2)吗,晕死
: o(n*lgn)基本没戏了,看能不能数学证明下这是不可能的

1 (共1页)
相关主题
Maximal Rectangle如果不要求是Rectangle就要简单得多Print out all elements in a sorted matrix
问一道算法题刚看到的一道google面试题
再来道题一个小公司面经
请教2个 huge file的面试题算法问题,m*m matrix
~~问两道AMAZON电面题有A[i]
请教一道careercup 150上的题问一道老题
大牛们看看这题:Find Peak Element IImatrix question
一道热门的 Google 面试题Amazon algorithm question, google
相关话题的讨论汇总
话题: int话题: node话题: mid话题: matrix话题: val