Τυχεροί αριθμοί σε μια λύση Matrix Leetcode


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις μαντείο
Παράταξη

Το πρόβλημα των τυχερών αριθμών σε ένα Matrix Leetcode Solution μας ζήτησε να βρούμε έναν τυχερό ακέραιο από τη συγκεκριμένη μήτρα. Ένας τυχερός ακέραιος ορίζεται ως ένας αριθμός που είναι ο ελάχιστος μεταξύ όλων των άλλων στοιχείων στη σειρά του και ο μέγιστος μεταξύ της στήλης του. Μπορεί να υπάρχουν περισσότεροι από ένας τυχεροί ακέραιοι αριθμοί στη δεδομένη μήτρα. Έχουμε λοιπόν την ελευθερία οποιουδήποτε από αυτά. Σε περίπτωση που δεν υπάρχει τυχερός αριθμός στη μήτρα, πρέπει να επιστρέψουμε έναν κενό φορέα. Επομένως, πριν βυθίσουμε βαθιά τη λύση, ας ρίξουμε μια ματιά σε μερικά παραδείγματα.

Τυχεροί αριθμοί σε μια λύση Matrix Leetcode

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

Επεξήγηση: 15 είναι ο ελάχιστος αριθμός στη σειρά του, καθώς και το μέγιστο στοιχείο στη στήλη του. Έτσι, το 15 επιστρέφεται ως έξοδος.

Προσέγγιση των τυχερών αριθμών σε μια λύση Matrix Leetcode

Το πρόβλημα Lucky Numbers σε ένα Matrix Leetcode Solution είναι ένα από τα τυπικά. Και ρωτάται πολύ συχνά σε πολλούς γύρους κωδικοποίησης. Το πρόβλημα είναι απλό, γιατί απλά πρέπει να ελέγξουμε εάν υπάρχει κάποιο στοιχείο που να είναι ελάχιστο στη σειρά του. Και ταυτόχρονα θα πρέπει να είναι το μέγιστο στη στήλη του. Έτσι, μπορούμε εύκολα να το κάνουμε αυτό, χρησιμοποιώντας δύο προσωρινές συστοιχίες. Αυτές οι συστοιχίες αποθηκεύουν το ελάχιστο στοιχείο κάθε σειράς και το μέγιστο στοιχείο κάθε στήλης.

Μετά από αυτό, πρέπει να ελέγξουμε εάν υπάρχει κάποιο στοιχείο που είναι κοινό και στις δύο αυτές προσωρινές συστοιχίες. Έτσι, μπορούμε να χρησιμοποιήσουμε HashSet όπου εισάγουμε τα στοιχεία ενός πίνακα. Στη συνέχεια, διασχίζουμε τα στοιχεία του δεύτερου πίνακα και ελέγχουμε εάν υπάρχει στο HashSet. Εάν υπάρχει κάποιο στοιχείο και στις δύο συστοιχίες, το επιστρέφουμε ως έξοδο. Αλλά αν δεν πάρουμε κανένα αγώνα, επιστρέφουμε ένα κενό διάνυσμα ως απάντηση.

Κωδικός για τυχερούς αριθμούς σε μια λύση Matrix 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), γιατί χρησιμοποιούμε δύο προσωρινές συστοιχίες.