2025年高频排序矩阵面试题及答案

2025年高频排序矩阵面试题及答案给定一个m×n的矩阵matrix，其中每行元素从左到右递增，每列元素从上到下递增。设计一个时间复杂度低于O(mn)的算法，判断目标值target是否存在于矩阵中。解题思路：利用矩阵行列双递增的特性，选择一个合适的起始点缩小搜索范围。由于右上角元素是该行最大、该列最小的元素（或左下角元素是该行最小、该列最大的元素），可通过比较目标值与该位置元素的大小，决定向左或向下移动指针。例如，若当前元素大于target，说明当前列下方元素都大于target，向左移动列指针；若当前元素小于target，说明当前行左侧元素都小于target，向下移动行指针。重复此过程直到找到目标或指针越界。Python代码实现：```pythondefsearch_matrix(matrix,target):ifnotmatrixornotmatrix[0]:returnFalsem,n=len(matrix),len(matrix[0])i,j=0,n1从右上角开始whilei<mandj>=0:ifmatrix[i][j]==target:returnTrueelifmatrix[i][j]>target:j-=1左移else:i+=1下移returnFalse```复杂度分析：时间复杂度O(m+n)，最坏情况下需要遍历所有行或列；空间复杂度O(1)，仅使用常数级额外空间。给定k个m×n的有序矩阵（每个矩阵内部行和列均递增），要求将所有矩阵中的元素合并为一个升序数组。解题思路：类似合并k个有序链表的思路，使用优先队列（最小堆）来维护当前各矩阵的最小候选元素。具体步骤：1.初始化堆，将每个矩阵的第一个元素（行优先遍历的第一个元素，即matrix[0][0]）及其坐标（矩阵索引、行索引、列索引）加入堆；2.每次从堆中弹出最小元素，将其加入结果数组；3.若该元素所在矩阵中还有下一个元素（即列未越界时右移，或列越界时行下移且列重置为0），则将下一个元素加入堆；4.重复直到堆为空。Python代码实现（使用heapq模块）：```pythonimportheapqdefmerge_k_sorted_matrices(matrices):ifnotmatrices:return[]heap=[]初始化堆：存储（值，矩阵索引，行，列）foridx,matinenumerate(matrices):ifmatandmat[0]:跳过空矩阵heapq.heappush(heap,(mat[0][0],idx,0,0))result=[]whileheap:val,mat_idx,row,col=heapq.heappop(heap)result.append(val)获取当前矩阵的下一个元素current_mat=matrices[mat_idx]ifcol+1<len(current_mat[0]):同一行下一列有元素next_row,next_col=row,col+1elifrow+1<len(current_mat):下一行第一列有元素next_row,next_col=row+1,0else:无后续元素continueheapq.heappush(heap,(current_mat[next_row][next_col],mat_idx,next_row,next_col))returnresult```复杂度分析：假设每个矩阵有m×n个元素，总共有k个矩阵，总元素数为k×m×n。堆的大小最大为k（每个矩阵贡献一个元素），每次堆操作时间复杂度为O(logk)，总时间复杂度为O(k×m×n×logk)；空间复杂度为O(k)（堆的大小）加上结果数组O(k×m×n)。给定一个n×n的矩阵matrix，其中每行和每列均按升序排列，找出矩阵中第k小的元素（k从1开始计数）。解题思路：采用二分查找法，通过统计矩阵中小于等于中间值的元素数量来调整搜索范围。具体步骤：1.初始化左边界left为matrix[0][0]，右边界right为matrix[-1][-1]；2.计算中间值mid=(left+right)//2，统计矩阵中≤mid的元素个数count；3.若count≥k，说明第k小元素≤mid，调整右边界为mid；若count<k，说明第k小元素>mid，调整左边界为mid+1；4.重复直到left≥right，此时left即为第k小元素。统计count时，利用每行递增的特性，从每行的最后一列开始向左遍历，找到该行中≤mid的最大列索引，累加该索引+1（元素个数）。Python代码实现：```pythondefkth_smallest(matrix,k):n=len(matrix)defcount_less_or_equal(mid):cnt=0row,col=0,n1从第一行最后一列开始whilerow<nandcol>=0:ifmatrix[row][col]<=mid:cnt+=col+1当前行前col+1个元素≤midrow+=1下一行else:col-=1当前行需要左移找更小元素returncntleft,right=matrix[0][0],matrix[-1][-1]whileleft<right:mid=(left+right)//2cnt=count_less_or_equal(mid)ifcnt>=k:right=midelse:left=mid+1returnleft```复杂度分析：二分查找的次数为O(log(max_valmin_val))，其中max_val和min_val是矩阵的最大和最小值；每次count_less_or_equal函数的时间复杂度为O(n)（每行最多遍历一次列），总时间复杂度为O(nlog(max_valmin_val))；空间复杂度为O(1)。给定一个m×n的矩阵matrix，将每条对角线上的元素（对角线上的元素满足i-j为定值）按升序排列后，返回修改后的矩阵。解题思路：利用对角线的特性（i-j的值唯一标识一条对角线），使用哈希表存储每条对角线上的元素，排序后再按原对角线顺序填充回矩阵。具体步骤：1.遍历矩阵，将每个元素matrix[i][j]加入键为i-j的哈希表列表中；2.对每个哈希表中的列表进行升序排序；3.再次遍历矩阵，按顺序从对应对角线的排序列表中取出元素，填充到原位置。Python代码实现：```pythonfromcollectionsimportdefaultdictdefdiagonal_sort(matrix):m,n=len(matrix),len(matrix[0])diagonals=defaultdict(list)收集所有对角线上的元素foriinrange(m):forjinrange(n):diagonals[ij].append(matrix[i][j])对每个对角线的元素排序forkeyindiagonals:diagonals[key].sort()重新填充矩阵foriinrange(m):forjinrange(n):当前对角线的元素列表，按顺序取第k个元素（k为当前遍历的顺序）key=ijmatrix[i][j]=diagonals[key].pop(0)弹出第一个元素（已排序）returnmatrix```复杂度分析：假设矩阵有m行n列，总元素数为m×n。收集和填充元素的时间复杂度为O(mn)；每条对角线的排序时间复杂度为O(dlogd)，其中d为对角线元素个数，所有对角线的总排序时间复杂度为O(mnlogd)（d最大为min(m,n)）。总时间复杂度为O(mnlogd)；空间复杂度为O(mn)（存储所有对角线元素）。给定一个行和列均递增的有序矩阵，将其顺时针旋转90度后，设计一个算法判断旋转后的矩阵是否仍保持行和列递增的有序性；若不能保持，说明如何调整可使其重新有序。解题思路：顺时针旋转90度后，原矩阵中元素matrix[i][j]的新位置为(j,n-1-i)（假设原矩阵为n×n）。旋转后的矩阵若要保持行和列递增，需满足新矩阵中每个元素大于等于其左侧和上方元素。由于原矩阵行递增（matrix[i][j]≤matrix[i][j+1]）、列递增（matrix[i][j]≤matrix[i+1][j]），旋转后新矩阵的行对应原矩阵的列逆序，列对应原矩阵的行逆序，因此旋转后的矩阵通常无法保持有序。例如，原矩阵：[[1,2,3],[4,5,6],[7,8,9]]顺时针旋转90度后为：[[7,4,1],[8,5,2],[9,6,3]]显然新矩阵的行和列均递减，不满足递增要求。若要使旋转后的矩阵重新有序，需将所有元素提取后排序，再按旋转后的顺序填充。具体步骤：1.将原矩阵所有元素存入列表并排序；2.按顺时针旋转后的顺序（即新矩阵的行优先顺序）将排序后的元素依次填充。Python代码实现（以n×n矩阵为例）：```pythondefrotate_and_sort(matrix):n=len(matrix)提取所有元素并排序elements=[]forrowinmatrix:elements.extend(row)elements.sort()顺时针旋转后的填充顺序：新矩阵的行i，列j对应原矩阵的列j，行n-1-i新矩阵的行优先遍历顺序为：行0列0→行0列1→…→行0列n-1→行1列0→…对应排序后的元素按顺序填充rotated=[[0]nfor_inrange(n)]idx=0forjinrange(n):原列j（新行i的列j）foriinreversed(range(n)):原行i从n-1到0（新行i）ifidx<len(elements):rotated[j][n-1i]=elements[idx]调整索引对应关系idx+=1returnrotated```复杂度分析：提取和排序元素的时间复杂度为O(n²logn)；填充新矩阵的时间复杂度为O(n²)，总时间复杂度为O(n²logn)；空间复杂度为O(n²)（存储排序后的元素）。给定一个部分有序的矩阵（仅保证每行递增，但列无序），设计一个算法找到矩阵中的最小值，要求时间复杂度低于O(mn)。解题思路：由于每行递增，每行的最小值为该行第一个元素，因此矩阵的最小值一定在所有行的第一个元素中。遍历所有行的第一个元素，取其中的最小值即可。若矩阵某些行为空，需跳过空行。Python代码实现：```pythondeffind_min_in_partially_sorted_mat