矩陣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), 因為我們使用了兩個臨時數組。