378. Kth Smallest Element in a Sorted Matrix

     /*
      * 378. Kth Smallest Element in a Sorted Matrix
      * 2016-8-17 by Mingyang
      * 一开始想用priority queue，但是发现时间太长，后来对于这种类型的matrix，
      * 就利用了240的方法计算比他小的个数，再利用k与这个结果的比较关系，进一步
      * 缩小所需要的时间，总时间是nlogn
      */
     public int kthSmallest(int[][] matrix, int k) {
            int n = matrix.length;
            int lo = matrix[0][0], hi = matrix[n - 1][n - 1];
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                int count = getLessEqual(matrix, mid);
                if (count < k) lo = mid + 1;
                else hi = mid - 1;
            }
            return lo;
        }
        private int getLessEqual(int[][] matrix, int val) {
            int res = 0;
            int n = matrix.length, i = n - 1, j = 0;
            while (i >= 0 && j < n) {
                if (matrix[i][j] > val) i--;
                else {
                    res += i + 1;
                    j++;
                }
            }
            return res;
        }