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

1. 题目解析与核心思路1380题要求我们找出矩阵中的幸运数。根据题目定义幸运数需要同时满足两个条件在所在行是最小值在所在列是最大值这个定义看似简单但实际处理时需要特别注意边界条件和效率问题。我们先来看一个具体例子给定矩阵 [ [3,7,8], [9,11,13], [15,16,17] ]在这个3x3矩阵中第一行最小值是3第一列检查第一列的最大值比较3,9,15 → 153不是该列最大值所以不是幸运数最终发现15满足条件它所在行最小所在列最大1.1 暴力解法分析最直观的解法是双重循环遍历每一行找到该行最小值及其列索引检查该值是否也是其所在列的最大值记录所有满足条件的数这种方法时间复杂度为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这个实现有几个关键点使用内置min()找出行最小值index()方法获取列索引列表推导式生成列数据比较是否为列最大值注意在Python中min()和max()的时间复杂度都是O(n)所以整体复杂度确实是O(m*n)2.2 优化方向虽然上述解法已经足够但我们还可以做一些优化预处理列最大值 可以先遍历一次矩阵记录每列的最大值这样后续检查时可以直接比较避免重复计算。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使用numpy库面试时不建议 如果允许使用第三方库numpy可以简化操作import numpy as np def luckyNumbers(matrix): arr np.array(matrix) return [x for x in arr.min(axis1) if x in arr.max(axis0)]不过要注意面试时通常要求不依赖第三方库。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 边界情况测试好的解法必须处理以下边界情况空矩阵返回[]单行矩阵该行最小值即为幸运数如果也是列最大值单列矩阵该列最大值即为幸运数如果也是行最小值所有元素相同所有元素都是幸运数矩阵中有重复值需要正确处理例如测试用例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. 算法扩展思考这个问题可以延伸出几个有趣的变种反向幸运数行最大值且列最小值幸运数对两个数互为行最小和列最大幸运数路径从幸运数开始只能移动到同行或同列的其他幸运数例如反向幸运数的解法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 lucky6. 实际应用场景虽然这个问题看起来是纯数学的但类似概念在实际中有重要应用鞍点问题在优化理论中鞍点是函数在某个方向上的最小值同时在另一个方向上的最大值博弈论矩阵博弈中的纯策略纳什均衡点就是这种幸运数数据清洗识别数据表中的异常值某特征最小但另一特征最大例如在推荐系统中我们可能要找出在用户维度评分最低但在物品维度评分最高 这样的争议性物品。7. 其他语言实现7.1 Java实现import java.util.ArrayList; import java.util.List; class Solution { public ListInteger luckyNumbers(int[][] matrix) { ListInteger 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: vectorint luckyNumbers(vectorvectorint matrix) { if (matrix.empty()) return {}; vectorint res; int m matrix.size(), n matrix[0].size(); vectorint 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, number10) t2 timeit.timeit(test_optimized, number10) t3 timeit.timeit(test_numpy, number10) print(fOriginal: {t1:.3f}s) print(fOptimized: {t2:.3f}s) print(fNumpy: {t3:.3f}s)典型结果可能如下Original: 4.732s Optimized: 2.153s Numpy: 0.847s可以看到预处理列最大值的优化版本比原始版本快约2倍而numpy版本由于底层优化更快。10. 总结与进阶挑战这道题很好地考察了对矩阵的基本操作能力。虽然题目简单但写出高效、清晰的代码需要扎实的基本功。我建议可以尝试以下进阶练习实现空间复杂度O(1)的解法不预处理列最大值处理超大矩阵无法一次性装入内存的情况并行化算法使用多线程或GPU加速实现一个生成随机测试用例的工具在实际面试中面试官可能会追问如何处理稀疏矩阵如果矩阵经常更新如何优化多次查询能否用线性代数的方法解决这个问题这些思考可以帮助你更深入地理解矩阵操作和算法优化。