ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಅದೃಷ್ಟ ಸಂಖ್ಯೆಗಳು


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಒರಾಕಲ್
ಅರೇ

ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಸಮಸ್ಯೆಯ ಲಕ್ಕಿ ಸಂಖ್ಯೆಗಳು ನಿರ್ದಿಷ್ಟ ಮ್ಯಾಟ್ರಿಕ್ಸ್‌ನಿಂದ ಅದೃಷ್ಟದ ಪೂರ್ಣಾಂಕವನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಮ್ಮನ್ನು ಕೇಳಿದೆ. ಅದೃಷ್ಟದ ಪೂರ್ಣಾಂಕವನ್ನು ಅದರ ಸಂಖ್ಯೆಯಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ, ಅದು ಅದರ ಸಾಲಿನಲ್ಲಿರುವ ಇತರ ಎಲ್ಲ ಅಂಶಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಮತ್ತು ಅದರ ಕಾಲಮ್‌ನಲ್ಲಿ ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ಕೊಟ್ಟಿರುವ ಮ್ಯಾಟ್ರಿಕ್ಸ್‌ನಲ್ಲಿ ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚು ಅದೃಷ್ಟ ಪೂರ್ಣಾಂಕ ಇರಬಹುದು. ಆದ್ದರಿಂದ ಅವುಗಳಲ್ಲಿ ಯಾವುದಾದರೂ ಒಂದು ಸ್ವಾತಂತ್ರ್ಯ ನಮಗೆ ಇದೆ. ಮ್ಯಾಟ್ರಿಕ್ಸ್‌ನಲ್ಲಿ ಯಾವುದೇ ಅದೃಷ್ಟ ಸಂಖ್ಯೆ ಇಲ್ಲದಿದ್ದರೆ, ನಾವು ಖಾಲಿ ವೆಕ್ಟರ್ ಅನ್ನು ಹಿಂತಿರುಗಿಸಬೇಕಾಗಿದೆ. ಆದ್ದರಿಂದ ದ್ರಾವಣದಲ್ಲಿ ಆಳವಾಗಿ ಧುಮುಕುವ ಮೊದಲು, ನಾವು ಕೆಲವು ಉದಾಹರಣೆಗಳನ್ನು ನೋಡೋಣ.

ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಅದೃಷ್ಟ ಸಂಖ್ಯೆಗಳು

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

ವಿವರಣೆ: 15 ಅದರ ಸಾಲಿನಲ್ಲಿರುವ ಕನಿಷ್ಠ ಸಂಖ್ಯೆ, ಮತ್ತು ಅದರ ಕಾಲಮ್‌ನ ಗರಿಷ್ಠ ಅಂಶವೂ ಆಗಿದೆ. ಹೀಗಾಗಿ 15 ಅನ್ನು .ಟ್‌ಪುಟ್‌ನಂತೆ ಹಿಂತಿರುಗಿಸಲಾಗುತ್ತಿದೆ.

ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಅದೃಷ್ಟ ಸಂಖ್ಯೆಗಳಿಗೆ ಅನುಸಂಧಾನ

ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿನ ಲಕ್ಕಿ ಸಂಖ್ಯೆಗಳ ಸಮಸ್ಯೆ ಪ್ರಮಾಣಿತವಾದದ್ದು. ಮತ್ತು ಅನೇಕ ಕೋಡಿಂಗ್ ಸುತ್ತುಗಳಲ್ಲಿ ಇದನ್ನು ಹೆಚ್ಚಾಗಿ ಕೇಳಲಾಗುತ್ತದೆ. ಸಮಸ್ಯೆ ಸರಳವಾಗಿದೆ ಏಕೆಂದರೆ ಅದರ ಸಾಲಿನಲ್ಲಿ ಕನಿಷ್ಠವಾಗಿರುವ ಯಾವುದೇ ಅಂಶವಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸಬೇಕಾಗಿದೆ. ಮತ್ತು ಅದೇ ಸಮಯದಲ್ಲಿ ಅದು ಅದರ ಕಾಲಂನಲ್ಲಿ ಗರಿಷ್ಠವಾಗಿರಬೇಕು. ಆದ್ದರಿಂದ, ಎರಡು ತಾತ್ಕಾಲಿಕ ಸರಣಿಗಳನ್ನು ಬಳಸುವ ಮೂಲಕ ನಾವು ಇದನ್ನು ಸುಲಭವಾಗಿ ಮಾಡಬಹುದು. ಈ ಸರಣಿಗಳು ಪ್ರತಿ ಸಾಲಿನ ಕನಿಷ್ಠ ಅಂಶ ಮತ್ತು ಪ್ರತಿ ಕಾಲಮ್‌ನ ಗರಿಷ್ಠ ಅಂಶವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತವೆ.

ಅದರ ನಂತರ, ಈ ಎರಡೂ ತಾತ್ಕಾಲಿಕ ಸರಣಿಗಳಲ್ಲಿ ಸಾಮಾನ್ಯವಾದ ಕೆಲವು ಅಂಶವಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸಬೇಕಾಗಿದೆ. ಆದ್ದರಿಂದ, ನಾವು ಬಳಸಬಹುದು ಹ್ಯಾಶ್‌ಸೆಟ್ ಅಲ್ಲಿ ನಾವು ಒಂದು ರಚನೆಯ ಅಂಶಗಳನ್ನು ಸೇರಿಸುತ್ತೇವೆ. ನಂತರ ನಾವು ಎರಡನೇ ರಚನೆಯ ಅಂಶಗಳ ಮೇಲೆ ಸಂಚರಿಸುತ್ತೇವೆ ಮತ್ತು ಅದು ಹ್ಯಾಶ್‌ಸೆಟ್‌ನಲ್ಲಿ ಇದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಎರಡೂ ಸರಣಿಗಳಲ್ಲಿ ಕೆಲವು ಅಂಶ ಇದ್ದರೆ ನಾವು ಅದನ್ನು .ಟ್‌ಪುಟ್‌ನಂತೆ ಹಿಂದಿರುಗಿಸುತ್ತೇವೆ. ಆದರೆ ಯಾವುದೇ ಹೊಂದಾಣಿಕೆ ಸಿಗದಿದ್ದರೆ, ನಾವು ಖಾಲಿ ವೆಕ್ಟರ್ ಅನ್ನು ಉತ್ತರವಾಗಿ ಹಿಂದಿರುಗಿಸುತ್ತೇವೆ.

ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಅದೃಷ್ಟ ಸಂಖ್ಯೆಗಳ ಕೋಡ್

ಸಿ ++ ಕೋಡ್

#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 ಗಳು ರಚನೆಯ ಸಾಲುಗಳು ಮತ್ತು ಕಾಲಮ್‌ಗಳಲ್ಲಿನ ಅಂಶಗಳಾಗಿವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ + ಎಂ), ಏಕೆಂದರೆ ನಾವು ಎರಡು ತಾತ್ಕಾಲಿಕ ಸರಣಿಗಳನ್ನು ಬಳಸುತ್ತೇವೆ.