1AC! Yes! Intuitive thought will be: we walk from up-left to down-right - but we should only walk along the ‘lowest edge‘ in the sorted matrix - so it is min-heap based BFS solution. Tricky, and really fun!
class Solution { struct Item { Item(): val(0), x(0), y(0){}; Item(int v, int xx, int yy): val(v), x(xx), y(yy){}; int val; int x; int y; // bool operator()(const Item &r1, const Item &r2) const { return r1.val > r2.val; } }; public: /** * @param matrix: a matrix of integers * @param k: an integer * @return: the kth smallest number in the matrix */ int kthSmallest(vector<vector<int> > &m, int k) { int h = m.size(); int w = m[0].size(); vector<vector<bool>> rec(h, vector<bool>(w, false)); priority_queue<Item, std::vector<Item>, Item> q; int i = 0, j = 0; Item ret; q.push(Item(m[i][j], j, i)); rec[i][j] = true; while(k) { ret = q.top();q.pop(); j = ret.x; i = ret.y; if(i < (h - 1) && !rec[i + 1][j]) { q.push(Item(m[i + 1][j], j, i + 1)); rec[i + 1][j] = true; } if(j < (w - 1) && !rec[i][j + 1]) { q.push(Item(m[i][j + 1], j + 1, i)); rec[i][j + 1] = true; } k--; } return ret.val; } };
LintCode "Kth Smallest Number in Sorted Matrix"
原文:http://www.cnblogs.com/tonix/p/4942849.html