矩阵中的幸运数 图解题解

要找的幸运数，到底长什么样

给一个 m 行 n 列、数字各不相同的矩阵 matrix。幸运数要同时满足两条：在它所在那一行里最小，在它所在那一列里又最大，缺一条都不算。要返回的是这些数本身，不是它们的行号列号，顺序随意。题面例子 matrix=[[3,7,8],[9,11,13],[15,16,17]] 的答案是 [15]，换成 [[7,8],[1,2]] 答案是 [7]。

照定义逐格验，慢在哪

一个数是不是幸运数，天然要看它那一行和那一列。照定义直接做，就对每个格子往它整行扫一遍确认最小、再往它整列扫一遍确认最大。矩阵有 m·n 个格子，每个都要花 m+n 的功夫核对，叠起来是 O(m·n·(m+n))，同一行、同一列被反复扫了很多遍，浪费全在这些重复上。

两份清单一取交，条件就凑齐了

这些重复是白费的：每行的最小、每列的最大各自只有一份，不必为每个格子重算。先扫一遍矩阵，把每行的最小值凑成集合 rows；再扫一遍，把每列的最大值凑成集合 cols。一个数在行里最小，它必然出现在 rows 里；在列里最大，必然出现在 cols 里。两个条件同时成立，等价于它同时落在两份集合中，也就是落在 rows 和 cols 的交集里。求出交集，就是全部幸运数。

三步走：行最小、列最大、求交集

落到三步。第一步逐行求最小，一行一行扫，每行记下最小的数丢进 rows。第二步逐列求最大，换成一列一列扫，每列记下最大的数丢进 cols。第三步求交集，既在 rows 又在 cols 里的数就是幸运数，收集返回。参考代码里 min(row) 求行最小、zip 星号 matrix 把矩阵转置后对每行 max 求出列最大，最后 rows & cols 求交集并返回列表。

拿题面的 3×3 矩阵，两趟扫下来看结果

逐行求最小：第 0 行 3、7、8 里最小是 3，第 1 行 9、11、13 里最小是 9，第 2 行 15、16、17 里最小是 15，rows={3,9,15}。逐列求最大：第 0 列 3、9、15 里最大是 15，第 1 列 7、11、16 里最大是 16，第 2 列 8、13、17 里最大是 17，cols={15,16,17}。求交集：3 和 9 都不在 cols，只有 15 两边都有——它在第 2 行里最小、又在第 0 列里最大，答案 [15]。

复杂度，还有两处一记反就全错

求每行最小、每列最大各把矩阵完整扫一遍，都是 O(m·n)，整体由扫矩阵主导，时间 O(m·n)；两份集合分别存 m 个和 n 个数，空间 O(m+n)。最坑的是把两条件记反——它要行里最小、列里最大，按行最大列最小去找，方向一反答案全错。另一种漏法是只验了行最小就下结论：题面里第 0 行最小 3、第 1 行最小 9 都是各自行里最小，可它俩所在列的最大都是 15，漏验列这一半，就会把 3 和 9 也误当幸运数。数字各不相同时幸运数至多一个，不必操心去重。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        rows = {min(row) for row in matrix}
        cols = {max(col) for col in zip(*matrix)}
        return list(rows & cols)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> luckyNumbers(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int rows[m];
        int cols[n];
        memset(rows, 0x3f, sizeof(rows));
        memset(cols, 0, sizeof(cols));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                rows[i] = min(rows[i], matrix[i][j]);
                cols[j] = max(cols[j], matrix[i][j]);
            }
        }
        vector<int> ans;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rows[i] == cols[j]) {
                    ans.push_back(rows[i]);
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public List<Integer> luckyNumbers(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] rows = new int[m];
        int[] cols = new int[n];
        Arrays.fill(rows, 1 << 30);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                rows[i] = Math.min(rows[i], matrix[i][j]);
                cols[j] = Math.max(cols[j], matrix[i][j]);
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rows[i] == cols[j]) {
                    ans.add(rows[i]);
                }
            }
        }
        return ans;
    }
}