Go 解法, 执行用时: 61ms, 内存消耗: 10432KB, 提交时间: 2022-05-31

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix int整型二维数组 
 * @param k int整型 
 * @return int整型
*/

func KthinMatrix( matrix [][]int ,  k int ) int {

	n := len(matrix)
	left := matrix[0][0]
	right := matrix[n-1][n-1]
	for left <= right{
		mid := left + (right-left)>>1
		if check(matrix,k,mid){
			right = mid - 1
		}else {
			left = mid + 1
		}
	}
	return left
}

func check(matrix [][]int,k int,mid int) bool {
	n := len(matrix)
	i := n-1
	j := 0
	sum := 0
	for i>=0&&j<n{
		if matrix[i][j] > mid{
			i--
		}else{
			j++
			sum += i + 1 //一列都加上
		}
	}
	return sum>=k
}

Go 解法, 执行用时: 62ms, 内存消耗: 9604KB, 提交时间: 2022-07-03

package main

func KthinMatrix(matrix [][]int, k int) int {
	h := len(matrix)
	m := matrix[0][0]
	n := matrix[h-1][h-1]
	for m <= n {
		mid := m + (n-m)>>1
		if find(matrix, k, mid) {
			n = mid - 1
		} else {
			m = mid + 1
		}
	}
	return m
}
func find(matrix [][]int, k int, mid int) bool {
	h := len(matrix)
	i := h - 1
	j := 0
	count := 0
	for i >= 0 && j < h {
		if matrix[i][j] > mid {
			i--
		} else {
			j++
			count += i + 1
		}
	}
	return count >= k
}

C++ 解法, 执行用时: 73ms, 内存消耗: 6380KB, 提交时间: 2022-06-01

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     * @param k int整型 
     * @return int整型
     */
    int findCount(vector<vector<int> >& matrix, int data)
    {
        int i=0,j=matrix[0].size()-1;
        int count=0;
        while(i<matrix.size()&&j>=0)
        {
            if(matrix[i][j]>data)
                j--;
            else
            {
                count+=j+1;
                i++;
            }
        }
        return count;
    }
    int KthinMatrix(vector<vector<int> >& matrix, int k) {
        // write code here
        int row=matrix.size();
        if(row==0)    return 0;
        int col=matrix[0].size();
        
        int left=matrix[0][0],right=matrix[row-1][col-1];
        while(left<right)
        {
            int mid=(right-left)/2+left;
            if(findCount(matrix, mid)<k)
                left=mid+1;
            else
                right=mid;
        }
        return left;
    }
};
/*
int KthinMatrix(vector<vector<int> >& matrix, int k) {
        // write code here
        int row=matrix.size();
        if(row==0)    return 0;
        int col=matrix[0].size();
        priority_queue<int> q;
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                if(q.size()>=k&&q.top()>matrix[i][j])
                {
                    q.pop();
                    q.push(matrix[i][j]);
                }
                if(q.size()<k)    q.push(matrix[i][j]);
            }
        }
        return q.top();
    }
    */

C++ 解法, 执行用时: 73ms, 内存消耗: 6380KB, 提交时间: 2022-04-18

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     * @param k int整型 
     * @return int整型
     */
    bool check(vector<vector<int> >& matrix, int k, int n) {
        int i = matrix.size() - 1;
        int j = 0;
        int num = 0;
        while (i >= 0 && j < matrix.size()) {
            if (matrix[i][j] <= n) {
                num = num + (i + 1);
                j += 1;
            } else {
                i -= 1;
            }
        }
        return num >= k;
    }
    int KthinMatrix(vector<vector<int> >& matrix, int k) {
        // write code here
        int n = matrix.size();
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = (left + right) / 2;
            if (check(matrix, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

C++ 解法, 执行用时: 74ms, 内存消耗: 6376KB, 提交时间: 2022-07-03

class Solution {
  public:
    int findsum(vector<vector<int> >& matrix, int d) {
        int i = 0, j = matrix[0].size() - 1;
        int sum = 0;
        while (i < matrix.size() && j >= 0) {
            if (matrix[i][j] > d)
                j--;
            else {
                sum += j + 1;
                i++;
            }
        }
        return sum;
    }
    int KthinMatrix(vector<vector<int> >& matrix, int k) {
        int x = matrix.size();
        if (x == 0)    return 0;
        int y = matrix[0].size();
        int m = matrix[0][0], n = matrix[x - 1][y - 1];
        while (m < n) {
            int mid = (n - m) / 2 + m;
            if (findsum(matrix, mid) < k)
                m = mid + 1;
            else
                n = mid;
        }
        return m;
    }
};