মনোটোনিক অ্যারে লেটকোড সমাধান


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক ফেসবুক
বিন্যাস

সমস্যা বিবৃতি

"মনোটোনিক অ্যারে" সমস্যাটিতে আমাদের একটি অ্যারে দেওয়া হয়। আমাদের কাজটি অ্যারেটি কিনা তা যাচাই করা একঘেয়ে অ্যারে বা না।

মনোটোনিক অ্যারে এমন একটি অ্যারে যেখানে উপাদানগুলি ক্রমবর্ধমান ক্রমে বা ক্রমহ্রাসমান ক্রমে সাজানো হয়। অ্যারেটি যদি ক্রমবর্ধমান ক্রমে সাজানো হয় তবে একটি অ্যারের অ্যারের জন্য [], আরার [i] <= অ্যারে [i + 1]। ক্রমহ্রাসমান ক্রমে সাজানো অ্যারের জন্য, আরআর [i]> = আরআর [i + 1]।

ফাংশনটি সত্য হওয়া উচিত যখন কেবল অ্যারেটি একঘেয়ে হয়। অন্যথায়, মিথ্যা ফিরে।

উদাহরণ

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

ব্যাখ্যা:  প্রতিটি আমি আরারের জন্য প্রদত্ত অ্যারেতে [i]

অভিগমন

এই সমস্যাটি সমাধান করার জন্য মনোোটোনিক অ্যারে কী তা পরিষ্কার করে বোঝা জরুরি।

মনোটোনিক অ্যারে এমন একটি অ্যারে যেখানে আমরা যদি অ্যারের সূচকের সূচী সংখ্যা এবং মানের মধ্যে একটি গ্রাফ প্লট করি তবে তা হয় একঘেয়েমিক বৃদ্ধি বা হ্রাস গ্রাফকে রূপ দেয়। নীচের চিত্রটি একঘেয়ে বর্ধমান এবং হ্রাস গ্রাফ দেখায় shows

মনোটোনিক অ্যারেতে লেটকোড সমাধান

এই সমস্যাটির পদ্ধতির মতো, আমরা অ্যারেটিকে অতিক্রম করব এবং এটি পরীক্ষা করব by [i] <= অ্যারে [i + 1] দ্বারা এটি ক্রমবর্ধমান অ্যারে কিনা তা পরীক্ষা করব। যদি এটি ক্রমবর্ধমান অ্যারে হয় তবে প্রদত্ত অ্যারেটি একঘেয়ে অ্যারে হয় অন্যথায় আমরা আবার অ্যারেটি অতিক্রম করব এবং এটি [i]> = অ্যারে [i + 1] পরীক্ষা করে এটি হ্রাসমান অ্যারে কিনা তা পরীক্ষা করব। যদি এটি হ্রাসমান অ্যারে হয় তবে প্রদত্ত অ্যারেটি একঘেয়ে অ্যারে হয় অন্যথায় এটি একঘেয়ে অ্যারে নয়।

অ্যারে কেবলমাত্র একটি একক ট্র্যাভারসাল ব্যবহার করে বাড়ছে বা কমছে কিনা তাও আমরা পরীক্ষা করতে পারি। আমরা দুটি পতাকা isincr এবং isdec ব্যবহার করব এবং সত্য দিয়ে এটি আরম্ভ করব। যদি [[i]> এ [i + 1] হয় তবে আইকনসিআরটি মিথ্যা হয়ে যাবে এবং যদি এ [আই] <এ [আই + 1] হয় তবে ইসডেক মিথ্যা হয়ে যাবে। যদি অ্যারে একঘেয়ে হয় তবে কমপক্ষে একটি আইসিনক্র এবং ইসডেক সত্য হবে। যখন উভয়ই মিথ্যা মানে অ্যারে মনোটোনিক হয় না কারণ উভয় ভুয়া মানই অ্যারের মানটি বৃদ্ধি এবং হ্রাস উভয়ই বলে থাকে।

 

কোড

সি ++ মনোোটোনিক অ্যারে লেটকোড সমাধান

#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

মনোটোনিক অ্যারের জটিল বিশ্লেষণ

সময়ের জটিলতা

উপরের কোডটির সময় জটিলতা উপর) কারণ আমরা কেবল অ্যারেটি একবারে যাচ্ছি এটি একবারে একঘেয়ে অ্যারে কিনা তা যাচাই করার জন্য। এখানে এন হ'ল ইনপুট অ্যারের আকার।

স্থান জটিলতা

উপরের কোডটির স্পেস জটিলতা ও (1) কারণ আমরা উত্তর সংরক্ষণের জন্য কেবল একটি পরিবর্তনশীল ব্যবহার করছি।

তথ্যসূত্র