Find the_k_th smallest number in at row and column sorted matrix.

Have you met this question in a real interview?

Yes

Example

Given k =4and a matrix:

[
  [1 ,5 ,7],
  [3 ,7 ,8],
  [4 ,8 ,9],
]

return5

Challenge

Solve it in O(k log n) time where n is the bigger one between row size and column size.

line 10 empty() not emtpy() write slowly
line 16 use min_heap, later use min_heap, better use short name
line 49, better use other not right

check binary search method on value

class Solution {

public:

/\*\*

 \* @param matrix: a matrix of integers

 \* @param k: an integer

 \* @return: the kth smallest number in the matrix

 \*/

int kthSmallest\(vector<vector<int> > &matrix, int k\) {

    // write your code here

    if \(matrix.empty\(\) \|\| matrix\[0\].empty\(\)\) {

        return -1;

    }



    int n = matrix.size\(\), m = matrix\[0\].size\(\);

    int start = matrix\[0\]\[0\], end = matrix\[n - 1\]\[m - 1\];

    while \(start < end\) {

        int mid = start + \(end - start >> 1\);

        if \(getCount\(matrix, mid\) < k\) {

            start = mid + 1;

        } else {

            end = mid;

        }

    }

    return start;

}



int getCount\(vector<vector<int>>& matrix, int val\) {

    int cnt = 0, n = matrix.size\(\), m = matrix\[0\].size\(\);

    int i = 0, j = m - 1;

    while \(i < n && j >= 0\) {

        if \(matrix\[i\]\[j\] > val\) {

            --j;

        } else {

            cnt += j + 1;

            ++i;

        }

    }

    return cnt;

}

};

results matching ""

    No results matching ""