华为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 = n
        self.matrix = matrix
        
        ikx = {}
        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 += 1
            x, y = iix
            ikx[x][1] = y
            if ik ==k :
                return matrix[iix[0]][iix[1]]
        
    def get_maymin_iix(self, ikx):
        ikx2 = {}
        for i,point in ikx.items():
            x, y = point
            if y>=self.n-1:
                continue
            y = y+1
            if i>=1 and ikx[i-1][1]<y:
                continue
            ikx2[i] = [(x, y),self.matrix[x][y]]
        return ikx2
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

测试

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)
1
2
3
4
5
6
7
8