การผกผันทั่วโลกและท้องถิ่นใน C++

สมมติว่าเรามีการเรียงสับเปลี่ยน A ของ [0, 1, ..., N - 1] โดยที่ N คือความยาวของ A ตอนนี้จำนวนการผกผัน (ทั่วโลก) คือจำนวน i A[j]. และจำนวนการผกผันภายในคือจำนวน i ที่มี 0 <=i A[i+1] เราต้องคืนค่า จริง หากจำนวนการผกผันทั่วโลกเท่ากับจำนวนการผกผันในเครื่อง ดังนั้นหากอินพุตเป็น [1,0,2] ให้คืนค่า จริง เนื่องจากมีเพียงหนึ่งการผกผันในเครื่องและการผกผันทั่วโลกหนึ่งรายการ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• maxVal :=-1, n :=ขนาดของ A
• สำหรับ i ในช่วง 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