أرقام الحظ في حل Matrix Leetcode


مستوى الصعوبة سهل
كثيرا ما يطلب في أوراكل
مجموعة

طلبت منا أرقام الحظ في حل Matrix Leetcode إيجاد عدد صحيح محظوظ من المصفوفة المحددة. يتم تعريف العدد الصحيح المحظوظ بأنه الرقم الأدنى بين جميع العناصر الأخرى في صفه والحد الأقصى بين العمود. لذلك قد يكون هناك أكثر من رقم صحيح واحد في المصفوفة المعطاة. لذلك لدينا الحرية لأي واحد منهم. في حالة عدم وجود رقم حظ في المصفوفة ، نحتاج إلى إرجاع متجه فارغ. لذا قبل التعمق في الحل ، دعونا نلقي نظرة على بعض الأمثلة.

أرقام الحظ في حل Matrix Leetcode

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

Explanation: 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

كود جافا

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) ، لأننا نستخدم مصفوفتين مؤقتتين.