พาร์ทิชันอาร์เรย์ในช่วงเวลาที่ไม่ปะติดปะต่อกันใน C++

สมมติว่าเรามีอาร์เรย์ A เราต้องแบ่งอาร์เรย์ออกเป็นสองอาร์เรย์ย่อยด้านซ้ายและขวา -

• ทุกองค์ประกอบในอาร์เรย์ย่อยด้านซ้ายจะน้อยกว่าหรือเท่ากับทุกองค์ประกอบในอาร์เรย์ย่อยด้านขวา

• อาร์เรย์ย่อยด้านซ้ายและขวาไม่ว่างเปล่า

• อาร์เรย์ย่อยด้านซ้ายมีขนาดเล็กที่สุด

เราต้องหาความยาวของด้านซ้ายหลังจากการแบ่งพาร์ทิชันดังกล่าว รับประกันว่ามีการแบ่งพาร์ติชั่นดังกล่าว

ดังนั้นหากอินพุตเป็น [5,0,3,8,6] เอาต์พุตจะเป็น 3 เนื่องจากอาร์เรย์ด้านซ้ายจะเป็น [5,0,3] และอาร์เรย์ย่อยด้านขวาจะเป็น [8,6]

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

• n :=ขนาดของ A สร้างอาร์เรย์ maxx ของขนาด n

• minVal :=องค์ประกอบสุดท้ายของ A

• maxx[0] :=A[0]

• สำหรับฉันอยู่ในช่วง 1 ถึง n – 1

  • maxx[i] :=สูงสุดของ A[i] และ A[i – 1]

• ตอบ :=ขนาด A – 1

• สำหรับฉันอยู่ในช่วง n – 1 เหลือ 1

  • minVal :=ขั้นต่ำของ minVal และ A[i]

  • ถ้า minVal>=max[i – 1] แล้ว ans :=i

• กลับมาอีกครั้ง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int partitionDisjoint(vector <int>& A) {
      int n = A.size();
      vector <int> maxx(n);
      int minVal = A[n - 1];
      maxx[0] = A[0];
      for(int i = 1; i < n; i++){
         maxx[i] = max(A[i], maxx[i - 1]);
      }
      int ans = A.size() - 1;
      for(int i = n - 1; i >= 1; i--){
         minVal = min(minVal, A[i]);
         if(minVal >= maxx[i - 1]){
            ans = i;
         }
      }
      return ans;
   }
};
main(){
   vector<int> v1 = {5,0,3,8,6};
   Solution ob;
   cout << (ob.partitionDisjoint(v1));
}

อินพุต

[5,0,3,8,6]

ผลลัพธ์

3