# boards

JobHunting版 - find kth element in n*n sorted matrix

~~问两道AMAZON电面题有A[i]

Print out all elements in a sorted matrix求分析这题的时间复杂度

 1 (共1页)
b*****c

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

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

3

cupertino的.
s******u

4
ｍａｒｋ，觉得这个题目很有趣，有时间做做
l******a

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

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

7

1 1 1 1
1 2 2 2
1 2 2 2
1 2 2 2

b*****c

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

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

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

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

12
lol.
1 2 4
2 3 4
2 4 4
k=5就错了

【在 s******u 的大作中提到】
: ｍａｒｋ，觉得这个题目很有趣，有时间做做
s********k

13
kth element难道不是matrix[k/n][k%n-1]？
b*****c

14

【在 s********k 的大作中提到】
: kth element难道不是matrix[k/n][k%n-1]？
s********k

15

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

b*****c

16

【在 s********k 的大作中提到】
: 找 kth 最小 element？
T*******e

17

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

【在 b*****c 的大作中提到】
: 不过最小是不表意的，因为kth最小和kth最大两种说法是同一意思。
b*****c

18

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

b*****c

19
bump
D*********d

20

T(n) = 3*T(1/4n)+a?然后复杂度是多少？有点蒙。。

j********8

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)
{
}
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

22

b******g

23

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

j*******t

b*****c

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

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

27

cupertino的.
s******u

28
ｍａｒｋ，觉得这个题目很有趣，有时间做做
l******a

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

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

31

1 1 1 1
1 2 2 2
1 2 2 2
1 2 2 2

b*****c

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

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

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

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

36
lol.
1 2 4
2 3 4
2 4 4
k=5就错了

【在 s******u 的大作中提到】
: ｍａｒｋ，觉得这个题目很有趣，有时间做做
s********k

37
kth element难道不是matrix[k/n][k%n-1]？
b*****c

38

【在 s********k 的大作中提到】
: kth element难道不是matrix[k/n][k%n-1]？
s********k

39

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

b*****c

40

【在 s********k 的大作中提到】
: 找 kth 最小 element？

Print out all elements in a sorted matrix算法问题，m*m matrix

T*******e

41

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

【在 b*****c 的大作中提到】
: 不过最小是不表意的，因为kth最小和kth最大两种说法是同一意思。
b*****c

42

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

b*****c

43
bump
D*********d

44

T(n) = 3*T(1/4n)+a?然后复杂度是多少？有点蒙。。
j********8

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)
{
}
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

46

b******g

47

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

j*******t

b*****c

49

o(n*lgn)基本没戏了，看能不能数学证明下这是不可能的
h*********r

50

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

 1 (共1页)

Maximal Rectangle如果不要求是Rectangle就要简单得多Print out all elements in a sorted matrix

~~问两道AMAZON电面题有A[i]