एक मैट्रिक्स Leetcode समाधान में भाग्यशाली संख्या


कठिनाई स्तर आसान
में अक्सर पूछा ओरेकल
ऐरे

मैट्रिक्स लेटेकोड सॉल्यूशन समस्या में लकी नंबर ने हमें दिए गए मैट्रिक्स से भाग्यशाली पूर्णांक खोजने के लिए कहा। एक भाग्यशाली पूर्णांक को एक संख्या के रूप में परिभाषित किया जाता है जो अपनी पंक्ति में सभी अन्य तत्वों के बीच न्यूनतम है और इसके स्तंभ के बीच अधिकतम है। तो दिए गए मैट्रिक्स में एक से अधिक भाग्यशाली पूर्णांक हो सकते हैं। तो हम उनमें से किसी एक की स्वतंत्रता है। यदि मैट्रिक्स में कोई भाग्यशाली संख्या नहीं है, तो हमें खाली वेक्टर को वापस करना होगा। तो समाधान में गहराई से गोता लगाने से पहले, आइए कुछ उदाहरणों पर गौर करें।

एक मैट्रिक्स Leetcode समाधान में भाग्यशाली संख्या

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

स्पष्टीकरण: 15 इसकी पंक्ति में न्यूनतम संख्या है, और इसके कॉलम में अधिकतम तत्व भी है। इस प्रकार 15 को आउटपुट के रूप में लौटाया जा रहा है।

एक मैट्रिक्स Leetcode समाधान में भाग्यशाली संख्या के लिए दृष्टिकोण

मैट्रिक्स लेटेकोड सॉल्यूशन में लकी नंबर की समस्या मानक लोगों में से एक है। और कई कोडिंग राउंड में बहुत बार पूछा जाता है। समस्या सरल है क्योंकि हमें यह जांचने की आवश्यकता है कि क्या कोई तत्व मौजूद है जो इसकी पंक्ति में न्यूनतम है। और उसी समय यह अपने कॉलम में अधिकतम होना चाहिए। तो, हम दो अस्थायी सरणियों का उपयोग करके, इसे आसानी से कर सकते हैं। ये सरणियाँ प्रत्येक पंक्ति के न्यूनतम तत्व और प्रत्येक स्तंभ के अधिकतम तत्व को संग्रहीत करती हैं।

उसके बाद, हमें यह जांचने की आवश्यकता है कि क्या कोई तत्व मौजूद है जो इन दोनों अस्थायी सरणियों में आम है। तो, हम उपयोग कर सकते हैं हैशसेट जहां हम एक सरणी के तत्वों को सम्मिलित करते हैं। फिर हम दूसरे एरे के तत्वों पर चलते हैं और यह जांचते हैं कि क्या यह हशसेट में मौजूद है। अगर कुछ तत्व दोनों सरणियों में मौजूद हैं तो हम इसे आउटपुट के रूप में वापस करते हैं। लेकिन अगर w को कोई मैच नहीं मिलता है, तो हम उत्तर के रूप में एक खाली वेक्टर लौटाते हैं।

एक मैट्रिक्स 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

जटिलता विश्लेषण

समय जटिलता

ओ (एन * एम), जहाँ N और M सरणी की पंक्तियों और स्तंभों में तत्व हैं।

अंतरिक्ष जटिलता

ओ (एन + एम), क्योंकि हम दो अस्थायी सरणियों का उपयोग करते हैं।