题目：力扣
解题思路：
先变成一维数组，再利用快速排序，找到第K小的。没有利用原二维数组有序的特性。时间复杂度为，空间复杂度
其实这道题当时一看就考虑能不能用二分查找，因为它从左上到右下是有序的，但想了一会还是没想到解决方案，后面看了题解，是利用一条分割线，具体可以看题解
class Solution { public int kthSmallest(int[][] matrix, int k) { int row = matrix.length; int col = matrix[0].length; int[] arr = new int[row*col]; int cnt = 0; for(int i = 0; i < row; i++){ for(int j = 0; j < col; j++){ arr[cnt++]=matrix[i][j]; } } return quickSort(arr, 0, arr.length-1, k-1); } public int quickSort(int[] arr, int start, int end, int k){ if(start == end){ return arr[start]; } int p = partition(arr, start, end); if(p == k){ return arr[p]; } else if(p <k){ return quickSort(arr, p+1, end, k); } else{ return quickSort(arr, start, p-1, k); } } public int partition(int[] arr, int start, int end){ int base = arr[start]; int l = start, r= end; while(l < r){ while(l < r && arr[r] >= base){ r--; } arr[l] = arr[r]; while(l < r && arr[l] < base){ l++; } arr[r] = arr[l]; } arr[l] = base; return l; } }
