给定一个 的矩阵,每行每列都是升序排列的,请你找到矩阵中第 K 小的元素
数据范围:
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]; }