იღბლიანი რიცხვები მატრიცის Leetcode ხსნარში


Რთული ტური Easy
ხშირად ეკითხებიან Oracle
Array

Lucky Numbers in Matrix Leetcode Solution პრობლემას გვთხოვა მოცემული მატრიციდან იპოვოთ იღბლიანი რიცხვი. იღბლიანი მთელი რიცხვი განისაზღვრება როგორც რიცხვი, რომელიც მინიმუმია რიგის ყველა სხვა ელემენტთან და მაქსიმუმი მის სვეტში. ამ მოცემულ მატრიცაში შეიძლება იყოს ერთზე მეტი იღბლიანი მთელი რიცხვი. ასე რომ, ჩვენ გვაქვს თავისუფლება რომელიმე მათგანისა. იმ შემთხვევაში, თუ მატრიცაში არ არის იღბლიანი რიცხვი, ჩვენ უნდა დავაბრუნოთ ცარიელი ვექტორი. სანამ ხსნარში სიღრმეში ჩავუღრმავდებით, გადახედეთ რამდენიმე მაგალითს.

იღბლიანი რიცხვები მატრიცის Leetcode ხსნარში

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

განმარტება: 15 არის მისი მწკრივის მინიმალური რიცხვი და ასევე მისი სვეტის მაქსიმალური ელემენტი. ამრიგად, 15 უბრუნდება გამომავალს.

იღბლიანი რიცხვების მიდგომა მატრიცის Leetcode ამოხსნაში

პრობლემა Lucky Numbers in Matrix Leetcode Solution არის ერთ – ერთი სტანდარტული. და მას ხშირად სთხოვენ მრავალ კოდირების რაუნდში. პრობლემა მარტივია, რადგან ჩვენ უბრალოდ უნდა გადავამოწმოთ, არსებობს თუ არა რაიმე ელემენტი, რომელიც მის რიგში მინიმალურია. ამავე დროს, ეს უნდა იყოს მაქსიმალური მის სვეტში. ასე რომ, ამის გაკეთება მარტივად შეგვიძლია, ორი დროებითი მასივის გამოყენებით. ეს მასივები ინახავს თითოეული მწკრივის მინიმალურ ელემენტს და თითოეული სვეტის მაქსიმალურ ელემენტს.

ამის შემდეგ, ჩვენ უნდა გადავამოწმოთ, არსებობს თუ არა რაიმე ელემენტი, რომელიც საერთოა ამ დროებით მასივებში. ასე რომ, ჩვენ შეგვიძლია გამოვიყენოთ 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

ჯავის კოდი

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), რადგან ვიყენებთ ორ დროებით მასივს.