1380. 矩阵中的幸运数

方法一：按要求遍历

• 对每个元素，判断行列中是否符合要求

class Solution {
public:
  vector<int> luckyNumbers (vector<vector<int>>& matrix) {
    vector<int> res;
    for (int i = 0; i < matrix.size(); i++) {
      for (int j = 0; j < matrix[0].size(); j++) {
        bool is_min = true, is_max = true;
        for (int k = 0; k < matrix.size(); k++) {
          if (matrix[k][j] < matrix[i][j]) {
            is_min = false;
            continue;
          }
        }
        if (is_min == false) continue;
        for (int l = 0; l < matrix[0].size(); l++) {
          if (matrix[i][l] > matrix[i][j]) {
            is_max = false;
            continue;
          }
        }
        if (is_max == false)continue;
        res.push_back(matrix[i][j]);
      }
    }
    return res;
  }  
}

方法二：哈希表处理

• 使用哈希表分别记录行最小值和列最大值，如果两个表中行列互相对应，那么这个值就符合要求。

class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        map<int, int> hash_ro, hash_co;
        for(int i = 0; i < matrix.size(); i++) {
            int idx = 0;
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] < matrix[i][hash_ro[i]]) {
                    hash_ro[i] = j;
                }
                if (matrix[i][j] > matrix[hash_co[j]][j]) {
                    hash_co[j] = i;
                }
            }
        }
        vector<int> res;
        for(auto iter : hash_ro) {
            if (hash_co[iter.second] == iter.first) {
                res.push_back(matrix[iter.first][iter.second]);
            }
        }
        return res;

    }
};

方法三：预处理

• 提前计算出行最小和列最大，如果一个值和行列最小最大值对应，那么这个值就符合要求。

class Solution {
public:
  vector<int> luckyNumbers (vector<vector<int>>& matrix) {
    vector<int> min_Row(matrix.size(), INT_MAX), max_Col(matrix[0].size(), 0);
    for (int i = 0; i < matrix.size(); i++) {
      for (int j = 0; j < matrix[0].size(); j++) {
        min_Row[i] = min(min_Row[i], matrix[i][j]);
        max_Col[j] = max(max_Col[j], matrix[i][j]);
      }
    }
    vector<int> res;
    for (int i = 0; i < matrix.size(); i++) {
      for (int j = 0; j < matrix[0].size(); j++) {
        if (matrix[i][j] == min_Row[i] && matrix[i][j] == max_Col[j]) {
          res.push_back(matrix[i][j]);
        }
      }
    }
    return res;
  }
};