Bir Matris Leetcode həllində uğurlu nömrələr

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Kahin
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 35

Bir Matrix Leetcode Həlli problemindəki uğurlu ədədlər, verilmiş matrisdən şanslı bir ədədi tapmağımızı istədi. Şanslı bir tam sıra, satırındakı bütün digər elementlər arasında minimum və sütun arasında maksimum olan bir rəqəm olaraq təyin olunur. Beləliklə, verilmiş matrisdə birdən çox şanslı ədədi ola bilər. Beləliklə, onlardan hər hansı birinin azadlığına sahibik. Matrisdə uğurlu bir rəqəm olmadığı təqdirdə boş bir vektor qaytarmalıyıq. Buna görə həll yoluna dərindən girmədən əvvəl bir neçə nümunəyə nəzər salaq.

Bir Matris Leetcode həllində uğurlu nömrələrPin

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

İzahat: 15 sıradakı minimum say və sütundakı maksimum elementdir. Beləliklə 15 çıxış olaraq geri qaytarılır.

Matrix Leetcode həllində uğurlu nömrələrə yanaşma

Matrix Leetcode həllindəki uğurlu ədədlər problemi standartlardan biridir. Bir çox kodlaşdırma turunda çox tez-tez soruşulur. Problem sadədir, çünki sıralarında minimum olan hər hansı bir elementin olub olmadığını yoxlamaq lazımdır. Və eyni zamanda sütunda maksimum olmalıdır. Beləliklə, iki müvəqqəti massivdən istifadə edərək bunu asanlıqla edə bilərik. Bu massivlər hər sətrin minimum elementini və hər sütunun maksimum elementini saxlayır.

Bundan sonra, hər iki müvəqqəti massivdə yayılmış bir elementin olub olmadığını yoxlamaq lazımdır. Beləliklə, istifadə edə bilərik HashSet burada bir sıra elementlərini daxil edirik. Sonra ikinci massivin elementlərini keçib HashSet-də olub olmadığını yoxlayırıq. Hər iki massivdə də bir element varsa, onu nəticə olaraq qaytarırıq. Ancaq heç bir uyğunlaşma olmazsa, cavab olaraq boş bir vektor qaytarırıq.

Bir Matris Leetcode Həllində Şanslı Nömrələr Kodu

C ++ kodu

#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 kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N * M), burada N və M massivin sətir və sütunlarındakı elementlərdir.

Kosmik Mürəkkəblik

O (N + M), çünki iki müvəqqəti massivdən istifadə edirik.

Şərh yaz

Translate »
1