मोनोटोनिक एरे लेटकोड समाधान


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना Facebook
ऐरे

समस्या का विवरण

"मोनोटोनिक एरे" समस्या में हमें एक सरणी दी जाती है। हमारा कार्य यह जांचना है कि सरणी ए है या नहीं एकरस सरणी या नहीं।

एक मोनोटोनिक सरणी एक सरणी है जहां तत्वों को या तो बढ़ते क्रम में या घटते क्रम में क्रमबद्ध किया जाता है। यदि सरणी को बढ़ते क्रम में क्रमबद्ध किया जाता है तो एक सरणी के लिए गिरफ्तारी [], गिरफ्तार [i] <= गिरफ्तारी [i + १]। घटते क्रम में क्रमबद्ध एक सरणी के लिए, गिरफ्तारी [i]> = गिरफ्तारी [i + 1]।

फ़ंक्शन केवल तभी लौटना चाहिए जब सरणी मोनोटोनिक हो। नहीं तो झूठा लौट आता है।

उदाहरण

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

स्पष्टीकरण:  प्रत्येक गिरफ्तारी के लिए दिए गए सरणी में [i]

दृष्टिकोण

इस समस्या को हल करने के लिए यह समझना बहुत महत्वपूर्ण है कि मोनोटोनिक सरणी क्या है।

एक मोनोटोनिक सरणी एक सरणी है जिसमें यदि हम सरणी के उस सूचकांक पर सूचकांक संख्या और मूल्य के बीच एक ग्राफ बनाते हैं तो यह ग्राफ में वृद्धि या घटते हुए या तो मोनोटोनिक बनाता है। नीचे दी गई छवि एक नीरस बढ़ती और घटती ग्राफ दिखाती है।

मोनोटोनिक ऐरे को लेकोडकोड समाधान

इस समस्या के लिए दृष्टिकोण की तरह है, हम सरणी की जाँच करेंगे और जाँच करेंगे कि क्या यह गिरफ्तारी से बढ़ती सरणी है [i] <= गिरफ्तारी [i + 1]। यदि यह बढ़ती हुई सरणी है तो दिए गए सरणी एक मोनोटोनिक सरणी है, अन्यथा हम सरणी को फिर से आगे बढ़ाएंगे और जाँचेंगे कि क्या यह गिरते हुए सरणी की जाँच करके गिरफ्तारी करता है [i]> = गिरफ्तारी [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) क्योंकि हम उत्तरों को संग्रहीत करने के लिए केवल एक चर का उपयोग कर रहे हैं।

संदर्भ