Java实现 LeetCode 378 有序矩阵中第K小的元素

378. 有序矩阵中第K小的元素

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。

请注意，它是排序后的第k小元素，而不是第k个元素。

示例:

matrix = [

   [ 1,  5,  9],

   [10, 11, 13],

   [12, 13, 15]

],

k = 8,

返回 13。

说明:

你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

class Solution {

     public int kthSmallest(int[][] matrix, int k) {

        int n = matrix.length;

        int left = matrix[0][0], right = matrix[n-1][n-1];

        while(left < right){

            int mid = (left + right)/2;

            int cnt = numMid(matrix, n, mid);

            //System.out.println(cnt);

            if(cnt >= k){

                right = mid ;

            } else {

                left = mid + 1;

            }

        }

        return right;

    }

    int numMid(int[][] matrix, int n, int mid){

        int i = 0, j = n - 1;

        int cnt = 0;

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

            if(matrix[i][j] > mid){

                j--;

            } else {

                cnt += (j+1);

                i++;

            }

        }

        return cnt;

    }

}

巴特西

Java实现 LeetCode 378 有序矩阵中第K小的元素

378. 有序矩阵中第K小的元素

最新文章

热门文章