C++ में वैश्विक और स्थानीय व्युत्क्रमण

मान लीजिए कि हमारे पास [0, 1, ..., N - 1] का कुछ क्रमचय A है, जहां N, A की लंबाई है। अब (वैश्विक) व्युत्क्रमों की संख्या i ए [जे]। और स्थानीय व्युत्क्रमों की संख्या 0 <=i A[i+1] के साथ i की संख्या है। हमें सत्य लौटना होगा यदि और केवल तभी जब वैश्विक व्युत्क्रमों की संख्या स्थानीय व्युत्क्रमों की संख्या के बराबर हो। इसलिए यदि इनपुट [1,0,2] जैसा है, तो सही लौटें, क्योंकि केवल एक स्थानीय उलटा और एक वैश्विक उलटा है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• maxVal:=-1, n:=A का आकार
• मैं के लिए 0 से n - 3 की सीमा में
  • maxVal :=अधिकतम A[i] और maxVal
  • यदि maxVal> A[i + 2], तो झूठी वापसी करें
• सही लौटें

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool isIdealPermutation(vector<int>& A) {
      int maxVal = -1;
      int n = A.size();
      for(int i = 0; i < n - 2; i++){
         maxVal = max(A[i], maxVal);
         if(maxVal > A[i + 2])
         return false;
      }
      return true;
   }
};
main(){
   vector<int> v = {1,0,2};
   Solution ob;
   cout << (ob.isIdealPermutation(v));
}

इनपुट

[1,0,2]

आउटपुट

1