2025年高頻排序矩陣面試題及答案給定一個m×n的矩陣matrix，其中每行元素從左到右遞增，每列元素從上到下遞增。設計一個時間復雜度低于O(mn)的算法，判斷目標值target是否存在于矩陣中。解題思路：利用矩陣行列雙遞增的特性，選擇一個合適的起始點縮小搜索范圍。由于右上角元素是該行最大、該列最小的元素（或左下角元素是該行最小、該列最大的元素），可通過比較目標值與該位置元素的大小，決定向左或向下移動指針。例如，若當前元素大于target，說明當前列下方元素都大于target，向左移動列指針；若當前元素小于target，說明當前行左側(cè)元素都小于target，向下移動行指針。重復此過程直到找到目標或指針越界。Python代碼實現(xiàn)：```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)，僅使用常數(shù)級額外空間。給定k個m×n的有序矩陣（每個矩陣內(nèi)部行和列均遞增），要求將所有矩陣中的元素合并為一個升序數(shù)組。解題思路：類似合并k個有序鏈表的思路，使用優(yōu)先隊列（最小堆）來維護當前各矩陣的最小候選元素。具體步驟：1.初始化堆，將每個矩陣的第一個元素（行優(yōu)先遍歷的第一個元素，即matrix[0][0]）及其坐標（矩陣索引、行索引、列索引）加入堆；2.每次從堆中彈出最小元素，將其加入結(jié)果數(shù)組；3.若該元素所在矩陣中還有下一個元素（即列未越界時右移，或列越界時行下移且列重置為0），則將下一個元素加入堆；4.重復直到堆為空。Python代碼實現(xiàn)（使用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:無后續(xù)元素continueheapq.heappush(heap,(current_mat[next_row][next_col],mat_idx,next_row,next_col))returnresult```復雜度分析：假設每個矩陣有m×n個元素，總共有k個矩陣，總元素數(shù)為k×m×n。堆的大小最大為k（每個矩陣貢獻一個元素），每次堆操作時間復雜度為O(logk)，總時間復雜度為O(k×m×n×logk)；空間復雜度為O(k)（堆的大?。┘由辖Y(jié)果數(shù)組O(k×m×n)。給定一個n×n的矩陣matrix，其中每行和每列均按升序排列，找出矩陣中第k小的元素（k從1開始計數(shù)）。解題思路：采用二分查找法，通過統(tǒng)計矩陣中小于等于中間值的元素數(shù)量來調(diào)整搜索范圍。具體步驟：1.初始化左邊界left為matrix[0][0]，右邊界right為matrix[-1][-1]；2.計算中間值mid=(left+right)//2，統(tǒng)計矩陣中≤mid的元素個數(shù)count；3.若count≥k，說明第k小元素≤mid，調(diào)整右邊界為mid；若count<k，說明第k小元素>mid，調(diào)整左邊界為mid+1；4.重復直到left≥right，此時left即為第k小元素。統(tǒng)計count時，利用每行遞增的特性，從每行的最后一列開始向左遍歷，找到該行中≤mid的最大列索引，累加該索引+1（元素個數(shù)）。Python代碼實現(xiàn)：```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```復雜度分析：二分查找的次數(shù)為O(log(max_valmin_val))，其中max_val和min_val是矩陣的最大和最小值；每次count_less_or_equal函數(shù)的時間復雜度為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代碼實現(xiàn)：```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列，總元素數(shù)為m×n。收集和填充元素的時間復雜度為O(mn)；每條對角線的排序時間復雜度為O(dlogd)，其中d為對角線元素個數(shù)，所有對角線的總排序時間復雜度為O(mnlogd)（d最大為min(m,n)）。總時間復雜度為O(mnlogd)；空間復雜度為O(mn)（存儲所有對角線元素）。給定一個行和列均遞增的有序矩陣，將其順時針旋轉(zhuǎn)90度后，設計一個算法判斷旋轉(zhuǎn)后的矩陣是否仍保持行和列遞增的有序性；若不能保持，說明如何調(diào)整可使其重新有序。解題思路：順時針旋轉(zhuǎn)90度后，原矩陣中元素matrix[i][j]的新位置為(j,n-1-i)（假設原矩陣為n×n）。旋轉(zhuǎn)后的矩陣若要保持行和列遞增，需滿足新矩陣中每個元素大于等于其左側(cè)和上方元素。由于原矩陣行遞增（matrix[i][j]≤matrix[i][j+1]）、列遞增（matrix[i][j]≤matrix[i+1][j]），旋轉(zhuǎn)后新矩陣的行對應原矩陣的列逆序，列對應原矩陣的行逆序，因此旋轉(zhuǎn)后的矩陣通常無法保持有序。例如，原矩陣：[[1,2,3],[4,5,6],[7,8,9]]順時針旋轉(zhuǎn)90度后為：[[7,4,1],[8,5,2],[9,6,3]]顯然新矩陣的行和列均遞減，不滿足遞增要求。若要使旋轉(zhuǎn)后的矩陣重新有序，需將所有元素提取后排序，再按旋轉(zhuǎn)后的順序填充。具體步驟：1.將原矩陣所有元素存入列表并排序；2.按順時針旋轉(zhuǎn)后的順序（即新矩陣的行優(yōu)先順序）將排序后的元素依次填充。Python代碼實現(xiàn)（以n×n矩陣為例）：```pythondefrotate_and_sort(matrix):n=len(matrix)提取所有元素并排序elements=[]forrowinmatrix:elements.extend(row)elements.sort()順時針旋轉(zhuǎn)后的填充順序：新矩陣的行i，列j對應原矩陣的列j，行n-1-i新矩陣的行優(yōu)先遍歷順序為：行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]調(diào)整索引對應關系idx+=1returnrotated```復雜度分析：提取和排序元素的時間復雜度為O(n2logn)；填充新矩陣的時間復雜度為O(n2)，總時間復雜度為O(n2logn)；空間復雜度為O(n2)（存儲排序后的元素）。給定一個部分有序的矩陣（僅保證每行遞增，但列無序），設計一個算法找到矩陣中的最小值，要求時間復雜度低于O(mn)。解題思路：由于每行遞增，每行的最小值為該行第一個元素，因此矩陣的最小值一定在所有行的第一個元素中。遍歷所有行的第一個元素，取其中的最小值即可。若矩陣某些行為空，需跳過空行。Python代碼實現(xiàn)：```pythondeffind_min_in_partially_sorted_mat