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 | |
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 |
|
|
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 的大作中提到】
: ｍａｒｋ，觉得这个题目很有趣，有时间做做
|
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 | |
D*********d
发帖数: 125 | 20 每次把矩阵划成4份，每次至少能够扔掉1/4，也就是说如果k>左上角的最大值，那么扔
掉左上角，如果k<右下角的最小值，那么扔掉右下角，这样不知道是不是
T(n) = 3*T(1/4n)+a?然后复杂度是多少？有点蒙。。 |
|
|
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 | |
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/~........
|
|
|
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 的大作中提到】
: ｍａｒｋ，觉得这个题目很有趣，有时间做做
|
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？
|
|
|
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 | |
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)基本没戏了，看能不能数学证明下这是不可能的
|
