华为OD技术面试-有序数组第K最小值

背景

2024-03-15华为od 二面，记录结题过程

378. 有序矩阵中第 K 小的元素 - 力扣（LeetCode） https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/submissions/512483717/

题目

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

示例 1：

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 输出：13

解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

分析

采用遍历的思路
这里有个特点

• 如果已有第m小，则红色部分必须都已排好序，且连续
• 且下一个 小的数，只能是 黄色部分
  

结果

代码

class Solution(object):def kthSmallest(self, matrix, k):""":type matrix: List[List[int]]:type k: int:rtype: int"""n = len(matrix)self.n = nself.matrix = matrixikx = {}for i in range(n):ikx[i] = [i, -1]iix = [] # 当前遍历点ik = 0      # 当前第N小while True:ikx2 = self.get_maymin_iix(ikx)if len(ikx2)==1:iix = list(ikx2.values())[0][0]else:iix = min(ikx2.items(), key=lambda x:x[1][1])[1][0]ik += 1x, y = iixikx[x][1] = yif ik ==k :return matrix[iix[0]][iix[1]]def get_maymin_iix(self, ikx):ikx2 = {}for i,point in ikx.items():x, y = pointif y>=self.n-1:continuey = y+1if i>=1 and ikx[i-1][1]<y:continueikx2[i] = [(x, y),self.matrix[x][y]]return ikx2

测试

matrix = [[1,5,9],[10,11,13],[12,13,15]]c = {0: [(0, 1), 5], 1: [(1, 0), 10]}c = Solution()c.kthSmallest(matrix, 8)