1.题目描述：

给你一个n * n矩阵matrix ，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个不同的元素。根据题意有两个信息值得注意，首先每行每列都是非递减数列（即递增数列中插入相等的元素），再就是重复数在计算第几小元素时也需要累计，就如下图中的13既是第7小元素，又是第8小元素，降低了解题难度。

2.暴力解法：将二维数组元素复制到一维数组中，直接对数组所有元素进行排序，再取k-1索引位置的数即可

class Solution {
    public int kthSmallest(int[][] matrix, int k) { 
        int[] arr = new int[matrix.length * matrix.length];
        int index = 0;
        for(int[] row:matrix){
            for(int i = 0;i < row.length;i++){
                arr[index++] = row[i];
            }
        }
        Arrays.sort(arr);
        return arr[k - 1];
    }
}

3.二分查找：在原来的二维数组上进行操作，大致模型是该数组从左上角到右下角数值不断增大，也就是说被查到的第K小元素x将数组分成了数值比他大比他小的两部分，并且x增大比他小的部分的数是递增的，这就是二分查找的大致模型。

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
    int m = matrix.length;
    int left = matrix[0][0], right = matrix[m - 1][m - 1];
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m && matrix[i][j] <= mid; j++) {
                count++;
            }
        }
        if (count < k){
            left = mid + 1;
        } else{
            right = mid - 1;
        } 
    }
    return left;
}
}

二分查找的代码还比较容易理解，其中双层for循环计算<=mid值的元素个数可以根据二维数组的性质进行优化，思路跟我写的图解leetcode240.搜索二维矩阵中的第三种方法对角查找/Z字形查找类似，只是在走格子的过程中（图解里的第二步）加入计小于当前值的个数，这里略过。上面代码中难理解的地方就是图下这一段，问题①：如何保证最后while程序退出时得到的left值一定是二维数组中的元素呢？不妨假设得到的left值不是数组中的元素，left是第K小的元素，则left大于左上角所有元素，那么left左上角中一定存在最大的数组元素x使得x也是第K小的元素，而下面得到的代码第一个if语句的含义则是，left为能使count<k成立的最小值，这与前述矛盾，因此while程序退出时返回的left值必在数组中。问题②：为何最后return返回的是left值而不是right值呢？实际上程序在运行中，取得的mid值不一定是数组里存在的元素，每次在获得的count=K成立时，程序不会立刻结束，right向左逼近时值就为left，left向右逼近时需要left+1（这是我实测了两个例子后发现的），再思考了一下如果某次mid对应的count=K，但mid非数组元素，根据问题①可知，会寻找到满足条件的在数组中的left值返回；如果某次mid对应的count=K，且mid为数组元素，那么当前mid值就为返回的结果，但是程序中mid还会-1进行后续判读，最终仍是通过left来逼近返回值。第二问可能还不是理解很透彻，希望有大佬指点谢谢！

if (count < k){
            left = mid + 1;
        } else{
            right = mid - 1;
        } 
    }
    return left;

4.堆排序：有能力了再更新。。