给定一个 的矩阵,每行每列都是升序排列的,请你找到矩阵中第 K 小的元素
数据范围:
#include <algorithm> #include <cmath> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix int整型vector<vector<>> * @param k int整型 * @return int整型 */ int KthinMatrix(vector<vector<int> >& matrix, int k) { // write code here int len=matrix[0].size(); vector<int>vec; for(int i=0;i<len;i++){ for(int j=0;j<len;j++){ vec.push_back(matrix[i][j]); } } sort(vec.begin(), vec.end()); return vec[k-1]; } };
package main import "sort" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix int整型二维数组 * @param k int整型 * @return int整型 */ func KthinMatrix( matrix [][]int , k int ) int { arr:=[]int{} for _,child:=range matrix{ arr=append(arr,child...) } sort.Ints(arr) return arr[k-1] }
void heapAdjust(int heap[],int i,int n){//调整以i为节点的子树 int cur=heap[i],j; for(j=i*2+1;j<n;j=j*2+1){//建立大根堆才能找到第k小元素 if(j<n-1&&heap[j]<heap[j+1])//比较兄弟结点的大小 j++; if(cur>=heap[j]) break; heap[i]=heap[j]; i=j; } heap[i]=cur; } int KthinMatrix(int** matrix, int matrixRowLen, int* matrixColLen, int k ) { int** arr=matrix; int row=matrixRowLen,col=*matrixColLen; int i,j,p=0,n=row*col; int* t=(int*)malloc(sizeof(int)*n); for(i=0;i<row;i++){//放到一维数组中 memcpy(t+p*col,arr[i],sizeof(int)*col); p++; } for(i=k/2-1;i>=0;i--){//前k个元素进行堆调整 heapAdjust(t,i,k); } for(i=k;i<n;i++){//后面元素一次和堆定元素比较 if(t[i]<t[0]){ t[0]=t[i]; heapAdjust(t,0,k); } } return t[0]; }
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param matrix int整型二维数组 # @param k int整型 # @return int整型 # class Solution: """ 题目: https://www.nowcoder.com/practice/c754e7a920614cba9b8b692ba9b20b5d?tpId=196&tqId=40447&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title= 参考: 大神:牛客278599503号 算法: 题目已知:矩阵行列均为n,每行、每列均按升序排序,寻找第k小的元素。我们知道最小元素为left = matrix[0][0],最大元素为right = matrix[-1][-1],我们在闭合区间[left, right]上,使用二分法,寻找满足条件的第k小元素。 函数check(target):用于统计小于等于target的元素个数count(根据二维矩阵的升序性质,我们可以选择左下角或者右上角进行作为起点),返回值:count是否大于等于k 当left < right时: 取mid = left + (right - left) >> 1 check(mid): 如果满足条件,说明第k小元素在区间[left, mid]中 否则:说明mid小了,第k小元素在区间[mid + 1, right]中 复杂度: 时间复杂度:O(logD * (n + n)) = O(nlogD), D为矩阵最大值与最小值的差值,check方法的复杂度为O(2n) = O(n) 空间复杂度:O(1) """ def KthinMatrix(self, matrix, k): # write code here def check(target): i, j = 0, n - 1 # 这里选择从右上角开始统计 count = 0 while i < n and j >= 0: if matrix[i][j] <= target: count += j + 1 i += 1 else: j -= 1 return count >= k n = len(matrix) left, right = matrix[0][0], matrix[-1][-1] while left < right: mid = left + (right - left) / 2 if check(mid): right = mid else: left = mid + 1 return left if __name__ == "__main__": sol = Solution() matrix, k = [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25]], 5 # matrix, k = [[1, 1, 1], [1, 1, 1], [1, 1, 1]], 5 # matrix, k = [[1, 2, 5], [3, 4, 6], [7, 8, 9]], 5 res = sol.KthinMatrix(matrix, k) print res
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix int整型ArrayList<ArrayList<>> * @param k int整型 * @return int整型 */ public int KthinMatrix(ArrayList<ArrayList<Integer>> matrix, int k) { // write code here int row = matrix.size(); int col = matrix.get(0).size(); Queue<Integer> queue = new PriorityQueue<>(); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { queue.add(matrix.get(i).get(j)); } } while (k > 1) { queue.poll(); k--; } return queue.poll(); } }