矩阵Leetcode解决方案中的幸运数字


难度级别 易得奖学金
经常问 神谕
排列

矩阵Leetcode解决方案中的幸运数字要求我们从给定的矩阵中找到一个幸运整数。 幸运整数定义为一个数字,该数字在其行中的所有其他元素中是最小值,在其列中是最大值。 因此,给定矩阵中可能有多个幸运整数。 因此,我们拥有其中任何一个的自由。 如果矩阵中没有幸运数字,我们需要返回一个空向量。 因此,在深入研究解决方案之前,让我们看一些示例。

矩阵Leetcode解决方案中的幸运数字

matrix = [[3,7,8],[9,11,13],[15,16,17]]
[15]

说明:15是其行中的最小数字,也是其列中的最大元素。 因此,将15作为输出返回。

矩阵Leetcode解决方案中的幸运数字方法

矩阵Leetcode解决方案中的幸运数字问题是标准的问题之一。 在许多编码回合中经常被问到。 问题很简单,因为我们只需要检查其行中是否存在最小的元素。 同时,它的列中应为最大值。 因此,我们可以通过使用两个临时数组轻松地做到这一点。 这些数组存储每一行​​的最小元素和每一列的最大元素。

之后,我们需要检查在这两个临时数组中是否存在一些共同的元素。 因此,我们可以使用 哈希集 我们在其中插入一个数组的元素。 然后,我们遍历第二个数组的元素,并检查它是否存在于HashSet中。 如果两个数组中都存在某个元素,我们将其作为输出返回。 但是,如果w没有得到任何匹配,我们将返回一个空向量作为答案。

矩阵Leetcode解决方案中的幸运数字代码

C ++代码

#include <bits/stdc++.h>
using namespace std;

vector<int> luckyNumbers (vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    vector<int> row(n, INT_MAX), col(m, INT_MIN);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            row[i] = min(row[i], matrix[i][j]);
    }
    unordered_set<int> s;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++)
            col[i] = max(col[i], matrix[j][i]);
    }
    for(int i=0;i<n;i++)
        s.insert(row[i]);
    for(int i=0;i<m;i++)
        if(s.count(col[i]))
            return {col[i]};
    return {};
}

int main(){
    vector<vector<int>> v = {{3,7,8},{9,11,13},{15,16,17}};
    vector<int> output = luckyNumbers(v);
    for(auto x: output)
        cout<<x;
}
15

Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<Integer> luckyNumbers (int[][] matrix) {
      int n = matrix.length;
      int m = matrix[0].length;
      int[] row = new int[n];
      for(int i=0;i<n;i++)
          row[i] = Integer.MAX_VALUE;
      int[] col = new int[m];
      for(int i=0;i<m;i++)
          col[i] = Integer.MIN_VALUE;
      for(int i=0;i<n;i++){
          for(int j=0;j<m;j++)
              row[i] = Math.min(row[i], matrix[i][j]);
      }
      HashSet<Integer> s = new HashSet<Integer>();
      for(int i=0;i<m;i++){
          for(int j=0;j<n;j++)
              col[i] = Math.max(col[i], matrix[j][i]);
      }
      for(int i=0;i<n;i++)
          s.add(row[i]);
      for(int i=0;i<m;i++)
          if(s.contains(col[i]))
              return new ArrayList(Arrays.asList((col[i])));
      return new ArrayList();
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int[][] matrix = {{3,7,8},{9,11,13},{15,16,17}};
    List<Integer> output = luckyNumbers(matrix);
    if(output.size() > 0)
      System.out.print(output.get(0));
    
  }
}
15

复杂度分析

时间复杂度

O(N * M), 其中N和M是数组的行和列中的元素。

空间复杂度

O(N + M), 因为我们使用了两个临时数组。