ಏಕತಾನತೆಯ ಅರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


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

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಮೊನೊಟೋನಿಕ್ ಅರೇ” ಸಮಸ್ಯೆಯಲ್ಲಿ ನಮಗೆ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗುತ್ತದೆ. ರಚನೆಯು ಎ ಎಂದು ಪರಿಶೀಲಿಸುವುದು ನಮ್ಮ ಕಾರ್ಯ ಏಕತಾನತೆಯ ರಚನೆ ಅಥವಾ ಇಲ್ಲ.

ಏಕತಾನತೆಯ ರಚನೆಯು ಒಂದು ಶ್ರೇಣಿಯಾಗಿದ್ದು, ಅಲ್ಲಿ ಅಂಶಗಳನ್ನು ಹೆಚ್ಚಿಸುವ ಕ್ರಮದಲ್ಲಿ ಅಥವಾ ಕಡಿಮೆಗೊಳಿಸುವ ಕ್ರಮದಲ್ಲಿ ವಿಂಗಡಿಸಲಾಗುತ್ತದೆ. ರಚನೆಯನ್ನು ಹೆಚ್ಚಿಸುವ ಕ್ರಮದಲ್ಲಿ ವಿಂಗಡಿಸಿದ್ದರೆ, ಒಂದು ಶ್ರೇಣಿಗೆ arr [], arr [i] <= arr [i + 1]. ಕಡಿಮೆಯಾಗುವ ಕ್ರಮದಲ್ಲಿ ವಿಂಗಡಿಸಲಾದ ಒಂದು ಶ್ರೇಣಿಗಾಗಿ, arr [i]> = arr [i + 1].

ರಚನೆಯು ಏಕತಾನತೆಯಾಗಿದ್ದಾಗ ಮಾತ್ರ ಕಾರ್ಯವು ನಿಜವಾಗಬೇಕು. ಇಲ್ಲದಿದ್ದರೆ, ಸುಳ್ಳನ್ನು ಹಿಂತಿರುಗಿ.

ಉದಾಹರಣೆ

arr={1,2,4,5}
true

ವಿವರಣೆ:  ಪ್ರತಿಯೊಂದಕ್ಕೂ ಕೊಟ್ಟಿರುವ ಶ್ರೇಣಿಯಲ್ಲಿ ನಾನು [i]

ಅಪ್ರೋಚ್

ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಏಕತಾನತೆಯ ರಚನೆ ಎಂದರೇನು ಎಂಬುದನ್ನು ಸ್ಪಷ್ಟವಾಗಿ ಅರ್ಥಮಾಡಿಕೊಳ್ಳುವುದು ಬಹಳ ಮುಖ್ಯ.

ಏಕತಾನತೆಯ ರಚನೆಯು ಒಂದು ಶ್ರೇಣಿಯಾಗಿದ್ದು, ಇದರಲ್ಲಿ ನಾವು ರಚನೆಯ ಆ ಸೂಚ್ಯಂಕದಲ್ಲಿ ಸೂಚ್ಯಂಕ ಸಂಖ್ಯೆ ಮತ್ತು ಮೌಲ್ಯದ ನಡುವೆ ಗ್ರಾಫ್ ಅನ್ನು ಯೋಜಿಸಿದರೆ ಅದು ಏಕತಾನತೆಯ ಹೆಚ್ಚುತ್ತಿರುವ ಅಥವಾ ಕಡಿಮೆಯಾಗುವ ಗ್ರಾಫ್ ಅನ್ನು ರೂಪಿಸುತ್ತದೆ. ಕೆಳಗಿನ ಚಿತ್ರವು ಏಕತಾನತೆಯ ಹೆಚ್ಚುತ್ತಿರುವ ಮತ್ತು ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಗ್ರಾಫ್ ಅನ್ನು ತೋರಿಸುತ್ತದೆ.

ಮೊನೊಟೋನಿಕ್ ಅರೇಗೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಈ ಸಮಸ್ಯೆಯ ವಿಧಾನವು ಹೀಗಿದೆ, ನಾವು ರಚನೆಯನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ ಮತ್ತು ಇದು ಅರ್ [i] <= arr [i + 1] ಅನ್ನು ಪರಿಶೀಲಿಸುವ ಮೂಲಕ ಹೆಚ್ಚುತ್ತಿರುವ ಶ್ರೇಣಿಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಅದು ಹೆಚ್ಚುತ್ತಿರುವ ರಚನೆಯಾಗಿದ್ದರೆ, ಕೊಟ್ಟಿರುವ ರಚನೆಯು ಏಕತಾನತೆಯ ರಚನೆಯಾಗಿದೆ, ಇಲ್ಲದಿದ್ದರೆ ನಾವು ಮತ್ತೆ ರಚನೆಯನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ ಮತ್ತು ಅದು [[]] = arr [i + 1] ಎಂದು ಪರಿಶೀಲಿಸುವ ಮೂಲಕ ಅದು ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಶ್ರೇಣಿಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಅದು ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ರಚನೆಯಾಗಿದ್ದರೆ ಕೊಟ್ಟಿರುವ ರಚನೆಯು ಏಕತಾನತೆಯ ರಚನೆಯಾಗಿದೆ, ಇಲ್ಲದಿದ್ದರೆ ಅದು ಏಕತಾನತೆಯ ರಚನೆಯಲ್ಲ.

ಒಂದೇ ಅಡ್ಡಹಾಯುವಿಕೆಯನ್ನು ಬಳಸಿಕೊಂಡು ರಚನೆಯು ಹೆಚ್ಚಾಗುತ್ತಿದೆಯೇ ಅಥವಾ ಕಡಿಮೆಯಾಗುತ್ತಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸಬಹುದು. ನಾವು ಎರಡು ಧ್ವಜಗಳನ್ನು isincr ಮತ್ತು isdec ಅನ್ನು ಬಳಸುತ್ತೇವೆ ಮತ್ತು ಅದನ್ನು ನಿಜದೊಂದಿಗೆ ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ. A [i]> A [i + 1] ಆಗ isincr ಸುಳ್ಳಾಗುತ್ತದೆ ಮತ್ತು A [i] <A [i + 1] ಆಗಿದ್ದರೆ isdec ಸುಳ್ಳಾಗುತ್ತದೆ. ರಚನೆಯು ಏಕತಾನತೆಯಾಗಿದ್ದರೆ ಕನಿಷ್ಠ ಒಂದು isincr ಮತ್ತು isdec ನಿಜವಾಗಲಿದೆ. ಎರಡೂ ಸುಳ್ಳು ಎಂದರೆ, ರಚನೆಯು ಏಕತಾನತೆಯಲ್ಲ, ಏಕೆಂದರೆ ಎರಡೂ ಸುಳ್ಳು ಮೌಲ್ಯಗಳು ರಚನೆಯ ಮೌಲ್ಯವು ಹೆಚ್ಚಾಗುತ್ತಿದೆ ಮತ್ತು ಕಡಿಮೆಯಾಗುತ್ತಿದೆ ಎಂದು ಸೂಚಿಸುತ್ತದೆ.

 

ಕೋಡ್

ಸಿ ++ ಮೊನೊಟೋನಿಕ್ ಅರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

#include <bits/stdc++.h> 
using namespace std; 
        bool isMonotonic(vector<int>& A) {
        bool isincr = true;
        bool isdec = true;
        int n=A.size();
        for (int i = 0; i < n- 1; ++i) {
            if (A[i] > A[i+1])
                isincr = false;
            if (A[i] < A[i+1])
               isdec = false;
        }

        return isincr || isdec;   
    }

int main() 
{ 
 vector<int> arr = {1,2,4,5}; 
 cout <<boolalpha;
 cout<<isMonotonic(arr)<<endl; 
 return 0;
}
true

ಜಾವಾ ಮೊನೊಟೋನಿಕ್ ಅರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

import java.util.Arrays; 
public class Tutorialcup {
    public  static  boolean isMonotonic(int[] A) {
        boolean isincr = true;
        boolean isdec = true;
        int n=A.length;
        for (int i = 0; i < n- 1; ++i) {
            if (A[i] > A[i+1])
                isincr = false;
            if (A[i] < A[i+1])
               isdec = false;
        }

        return isincr || isdec;   
}
  public static void main(String[] args) {
    int [] arr = {1,2,4,5}; 
    boolean ans= isMonotonic(arr);
    System.out.println(ans);
  }
}
true

ಏಕತಾನತೆಯ ರಚನೆಯ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯದ ಸಂಕೀರ್ಣತೆ

ಮೇಲಿನ ಕೋಡ್‌ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ ಓ (ಎನ್) ಏಕೆಂದರೆ ಇದು ಏಕತಾನತೆಯ ರಚನೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸಲು ನಾವು ಒಮ್ಮೆ ಮಾತ್ರ ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗುತ್ತಿದ್ದೇವೆ. ಇಲ್ಲಿ n ಎಂಬುದು ಇನ್ಪುಟ್ ರಚನೆಯ ಗಾತ್ರವಾಗಿದೆ.

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

ಮೇಲಿನ ಕೋಡ್‌ನ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ ಒ (1) ಏಕೆಂದರೆ ನಾವು ಉತ್ತರಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ವೇರಿಯೇಬಲ್ ಅನ್ನು ಮಾತ್ರ ಬಳಸುತ್ತಿದ್ದೇವೆ.

ಉಲ್ಲೇಖಗಳು