Lucky Numbers in a Matrix Leetcode Solution


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Պատգամախոս
Դասավորություն

Մատրիցայի Leetcode Solution լուծման մեջ բախտավոր թվերը խնդրեցին մեզ գտնել տվյալ մատրիցից բախտավոր ամբողջ թիվ: Բախտավոր ամբողջ թվով սահմանվում է որպես թիվ, որն իր շարքի մյուս բոլոր տարրերի մեջ նվազագույնն է և իր սյունակի մեջ առավելագույնը: Այսպիսով, տվյալ մատրիցում կարող է լինել մեկից ավելի հաջողակ ամբողջ թիվ: Այսպիսով, մենք ունենք նրանցից յուրաքանչյուրի ազատությունը: Այն դեպքում, երբ մատրիցում երջանիկ թիվ չկա, մենք պետք է վերադարձնենք դատարկ վեկտորը: Այսպիսով, նախքան լուծումը խորը սուզվելը, եկեք նայենք մի քանի օրինակների:

Lucky Numbers in a Matrix Leetcode Solution

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

Բացատրություն. 15-ը իր տողի նվազագույն թիվն է, և նաև իր սյունակի առավելագույն տարրը: Այսպիսով, 15-ը վերադարձվում է որպես արտադրանք:

Բախտավոր թվերին մոտեցում մատրիցային Leetcode լուծման մեջ

Մատրիցայի Leetcode լուծման մեջ Lucky Numbers- ի խնդիրը ստանդարտներից մեկն է: Եվ շատ հաճախ հարցվում է կոդավորման բազմաթիվ փուլերում: Խնդիրը պարզ է, քանի որ մենք պարզապես պետք է ստուգենք, արդյոք գոյություն ունի որևէ տարր, որն իր շարքում նվազագույնն է: Եվ միևնույն ժամանակ, այն պետք է առավելագույն լինի իր սյունակում: Այսպիսով, մենք կարող ենք հեշտությամբ դա անել ՝ օգտագործելով երկու ժամանակավոր զանգված: Այս զանգվածները պահում են յուրաքանչյուր շարքի նվազագույն տարրը և յուրաքանչյուր սյունակի առավելագույն տարրը:

Դրանից հետո մենք պետք է ստուգենք, արդյոք կա որևէ տարր, որը տարածված է և՛ այս ժամանակավոր զանգվածներում: Այսպիսով, մենք կարող ենք օգտագործել HashSet որտեղ մենք տեղադրում ենք մեկ զանգվածի տարրերը: Դրանից հետո մենք անցնում ենք երկրորդ զանգվածի տարրերը և ստուգում, արդյոք այն առկա է HashSet- ում: Եթե ​​որևէ զանգվածում ինչ-որ տարր առկա է, մենք այն վերադարձնում ենք որպես ելք: Բայց եթե մենք ոչ մի համընկնում չենք ստանում, մենք որպես պատասխան դատարկ վեկտոր ենք վերադարձնում:

Մատրիցային 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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N * M), որտեղ N և M- ը զանգվածի տողերի և սյունակների տարրերն են:

Տիեզերական բարդություն

O (N + M), քանի որ մենք օգտագործում ենք երկու ժամանակավոր զանգված: