Given a matrix of size N x M. For each row the elements are sorted in ascending order, and for each column the elements are also sorted in ascending order. Find the Kth smallest number in it.
Assumptions:
the matrix is not null, N > 0 and M > 0
K > 0 and K <= N * M
Examples:
{ {1, 3, 5, 7},
{2, 4, 8, 9},
{3, 5, 11, 15},
{6, 8, 13, 18} }
the 5th smallest number is 4
the 8th smallest number is 6
class Solution(object):
def kthSmallest(self, matrix, k):
n = len(matrix)
m = len(matrix[0])
min = matrix[0][0]
max = matrix[n-1][m-1]
mid = 0
count = 0
while min < max:
mid = (min + max)/2
for i in xrange(0,n):
for j in xrange(0,m):
if matrix[i][j] <= mid:
count += 1
if k <= count:
max = mid
else:
min = mid + 1
count = 0
return min
