C++ এ গ্লোবাল এবং লোকাল ইনভার্সন

ধরুন আমাদের কিছু পারমুটেশন A আছে [0, 1, ..., N - 1], যেখানে N হল A এর দৈর্ঘ্য। এখন (গ্লোবাল) ইনভার্সশনের সংখ্যা হল i A[j]। এবং স্থানীয় বিপরীতের সংখ্যা হল i এর সংখ্যা যার সাথে 0 <=i A[i+1]। আমাদের সত্যে ফিরতে হবে যদি এবং শুধুমাত্র যদি বিশ্বব্যাপী বিপর্যয়ের সংখ্যা স্থানীয় বিপরীত সংখ্যার সমান হয়। সুতরাং যদি ইনপুট [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