矩阵幸运数查找算法与Python实现

1. 题目解析与核心思路

1380题要求我们找出矩阵中的"幸运数"。根据题目定义，幸运数需要同时满足两个条件：

• 在所在行是最小值
• 在所在列是最大值

这个定义看似简单，但实际处理时需要特别注意边界条件和效率问题。我们先来看一个具体例子：

给定矩阵： [ [3,7,8], [9,11,13], [15,16,17] ]

在这个3x3矩阵中：

• 第一行最小值是3（第一列）
• 检查第一列的最大值：比较3,9,15 → 15
• 3不是该列最大值，所以不是幸运数
• 最终发现15满足条件（它所在行最小，所在列最大）

1.1 暴力解法分析

最直观的解法是双重循环：

1. 遍历每一行，找到该行最小值及其列索引
2. 检查该值是否也是其所在列的最大值
3. 记录所有满足条件的数

这种方法时间复杂度为O(m*n)，因为最坏情况下需要检查每个元素。对于m行n列的矩阵，我们需要：

• m次行遍历找最小值
• 最多m次列检查

虽然这不是最优解，但对于LeetCode的测试用例规模已经完全够用。下面我们来看具体实现。

2. Python实现与优化

2.1 基础实现版本

def luckyNumbers(matrix): lucky = [] for row in matrix: min_val = min(row) col_idx = row.index(min_val) column = [matrix[i][col_idx] for i in range(len(matrix))] if min_val == max(column): lucky.append(min_val) return lucky

这个实现有几个关键点：

1. 使用内置min()找出行最小值
2. index()方法获取列索引
3. 列表推导式生成列数据
4. 比较是否为列最大值

注意：在Python中，min()和max()的时间复杂度都是O(n)，所以整体复杂度确实是O(m*n)

2.2 优化方向

虽然上述解法已经足够，但我们还可以做一些优化：

1. 预处理列最大值： 可以先遍历一次矩阵，记录每列的最大值，这样后续检查时可以直接比较，避免重复计算。

def luckyNumbers(matrix): if not matrix: return [] # 预处理列最大值 col_max = [max(col) for col in zip(*matrix)] lucky = [] for row in matrix: min_val = min(row) col_idx = row.index(min_val) if min_val == col_max[col_idx]: lucky.append(min_val) return lucky

2. 使用numpy库（面试时不建议）： 如果允许使用第三方库，numpy可以简化操作：

import numpy as np def luckyNumbers(matrix): arr = np.array(matrix) return [x for x in arr.min(axis=1) if x in arr.max(axis=0)]

不过要注意，面试时通常要求不依赖第三方库。

3. 复杂度分析与边界情况

3.1 时间复杂度

• 原始解法：O(m*n)

  • 遍历每行找最小值：O(m*n)
  • 检查列最大值：最坏O(m^2)

• 优化解法：O(m*n)

  • 预处理列最大值：O(m*n)
  • 主循环：O(m*n)

虽然大O表示法相同，但优化后的实际运行时间会更好。

3.2 空间复杂度

• 原始解法：O(1)额外空间（不包括输出）
• 优化解法：O(n)存储列最大值

3.3 边界情况测试

好的解法必须处理以下边界情况：

1. 空矩阵：返回[]
2. 单行矩阵：该行最小值即为幸运数（如果也是列最大值）
3. 单列矩阵：该列最大值即为幸运数（如果也是行最小值）
4. 所有元素相同：所有元素都是幸运数
5. 矩阵中有重复值：需要正确处理

例如测试用例：

assert luckyNumbers([]) == [] assert luckyNumbers([[7]]) == [7] assert luckyNumbers([[1,1],[1,1]]) == [1,1] assert luckyNumbers([[1,2],[3,4]]) == [2]

4. 实际编码中的常见问题

4.1 索引越界

新手容易犯的错误是在获取列数据时忘记检查行数：

# 错误示例 column = [matrix[i][col_idx] for i in range(len(matrix[0]))] # 错误使用了列数

应该使用行数len(matrix)而不是len(matrix[0])。

4.2 重复计算

每次检查列最大值时都重新计算会导致效率低下：

# 低效写法 if min_val == max([matrix[i][col_idx] for i in range(len(matrix))]):

应该像优化版本那样预处理列最大值。

4.3 多重循环混淆

在嵌套循环中容易混淆行列索引：

# 容易混淆的写法 for i in range(len(matrix)): # 行 for j in range(len(matrix[0])): # 列 # 这里i,j容易混淆

建议使用有意义的变量名：

for row_idx in range(rows): for col_idx in range(cols):

5. 算法扩展思考

这个问题可以延伸出几个有趣的变种：

1. 反向幸运数：行最大值且列最小值
2. 幸运数对：两个数互为行最小和列最大
3. 幸运数路径：从幸运数开始只能移动到同行或同列的其他幸运数

例如反向幸运数的解法：

def reverseLucky(matrix): row_max = [max(row) for row in matrix] lucky = [] for j in range(len(matrix[0])): col = [matrix[i][j] for i in range(len(matrix))] min_val = min(col) if min_val in row_max: lucky.append(min_val) return lucky

6. 实际应用场景

虽然这个问题看起来是纯数学的，但类似概念在实际中有重要应用：

1. 鞍点问题：在优化理论中，鞍点是函数在某个方向上的最小值，同时在另一个方向上的最大值
2. 博弈论：矩阵博弈中的纯策略纳什均衡点就是这种"幸运数"
3. 数据清洗：识别数据表中的异常值（某特征最小但另一特征最大）

例如在推荐系统中，我们可能要找出：

• 在用户维度评分最低
• 但在物品维度评分最高 这样的"争议性"物品。

7. 其他语言实现

7.1 Java实现

import java.util.ArrayList; import java.util.List; class Solution { public List<Integer> luckyNumbers(int[][] matrix) { List<Integer> res = new ArrayList<>(); int m = matrix.length, n = matrix[0].length; int[] colMax = new int[n]; // 预处理列最大值 for (int j = 0; j < n; j++) { int max = Integer.MIN_VALUE; for (int i = 0; i < m; i++) { if (matrix[i][j] > max) max = matrix[i][j]; } colMax[j] = max; } // 检查每行最小值 for (int[] row : matrix) { int min = Integer.MAX_VALUE; int colIdx = -1; for (int j = 0; j < n; j++) { if (row[j] < min) { min = row[j]; colIdx = j; } } if (min == colMax[colIdx]) { res.add(min); } } return res; } }

7.2 C++实现

#include <vector> #include <algorithm> using namespace std; class Solution { public: vector<int> luckyNumbers(vector<vector<int>>& matrix) { if (matrix.empty()) return {}; vector<int> res; int m = matrix.size(), n = matrix[0].size(); vector<int> colMax(n, INT_MIN); // 预处理列最大值 for (int j = 0; j < n; ++j) { for (int i = 0; i < m; ++i) { colMax[j] = max(colMax[j], matrix[i][j]); } } // 检查每行最小值 for (auto& row : matrix) { int minVal = *min_element(row.begin(), row.end()); int colIdx = min_element(row.begin(), row.end()) - row.begin(); if (minVal == colMax[colIdx]) { res.push_back(minVal); } } return res; } };

8. 单元测试建议

完整的解决方案应该包含以下测试用例：

import unittest class TestLuckyNumbers(unittest.TestCase): def test_empty_matrix(self): self.assertEqual(luckyNumbers([]), []) def test_single_element(self): self.assertEqual(luckyNumbers([[5]]), [5]) def test_multiple_lucky(self): self.assertEqual(sorted(luckyNumbers([[1,1],[1,1]])), [1,1]) def test_rectangular_matrix(self): matrix = [ [1, 10, 4], [9, 3, 8], [15,16,17] ] self.assertEqual(luckyNumbers(matrix), [15]) def test_no_lucky(self): matrix = [ [1, 2], [3, 4] ] self.assertEqual(luckyNumbers(matrix), [2]) if __name__ == '__main__': unittest.main()

9. 性能对比测试

让我们比较三种实现的性能：

import timeit import random def generate_test_case(m, n): return [[random.randint(1, 1000) for _ in range(n)] for _ in range(m)] # 测试数据 matrix = generate_test_case(1000, 1000) # 测试函数 def test_original(): luckyNumbers_original(matrix) def test_optimized(): luckyNumbers_optimized(matrix) def test_numpy(): luckyNumbers_numpy(matrix) # 计时 t1 = timeit.timeit(test_original, number=10) t2 = timeit.timeit(test_optimized, number=10) t3 = timeit.timeit(test_numpy, number=10) print(f"Original: {t1:.3f}s") print(f"Optimized: {t2:.3f}s") print(f"Numpy: {t3:.3f}s")

典型结果可能如下：

Original: 4.732s Optimized: 2.153s Numpy: 0.847s

可以看到预处理列最大值的优化版本比原始版本快约2倍，而numpy版本由于底层优化更快。

10. 总结与进阶挑战

这道题很好地考察了对矩阵的基本操作能力。虽然题目简单，但写出高效、清晰的代码需要扎实的基本功。我建议可以尝试以下进阶练习：

1. 实现空间复杂度O(1)的解法（不预处理列最大值）
2. 处理超大矩阵（无法一次性装入内存的情况）
3. 并行化算法（使用多线程或GPU加速）
4. 实现一个生成随机测试用例的工具

在实际面试中，面试官可能会追问：

• 如何处理稀疏矩阵？
• 如果矩阵经常更新，如何优化多次查询？
• 能否用线性代数的方法解决这个问题？

这些思考可以帮助你更深入地理解矩阵操作和算法优化。