Nghịch đảo toàn cục và cục bộ trong C ++

Giả sử chúng ta có một số hoán vị A của [0, 1, ..., N - 1], trong đó N là độ dài của A. Bây giờ số nghịch đảo (toàn cục) là số i A [j]. Và số nghịch đảo cục bộ là số i với 0 <=i A [i + 1]. Chúng ta phải trả về true nếu và chỉ khi số lần nghịch đảo toàn cục bằng số lần nghịch đảo cục bộ. Vì vậy, nếu đầu vào giống như [1,0,2], thì trả về true, vì chỉ có một đảo cục bộ và một đảo ngược toàn cục.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• maxVal:=-1, n:=kích thước của A
• cho tôi trong phạm vi từ 0 đến n - 3
  • maxVal:=max của A [i] và maxVal
  • nếu maxVal> A [i + 2], thì trả về false
• trả về true

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[1,0,2]

Đầu ra

1