home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Max Chunks เพื่อสร้าง Sorted II ใน C ++

สมมติว่าเรามีอาร์เรย์ arr ของจำนวนเต็ม เราต้องแยกอาร์เรย์ออกเป็นพาร์ติชั่นจำนวนหนึ่ง และเรียงลำดับแต่ละพาร์ติชั่นแยกกัน ตอนนี้หลังจากเชื่อมเข้าด้วยกันแล้วเราจะได้อาร์เรย์ที่จัดเรียงมาหนึ่งชุด เราต้องหาจำนวนพาร์ติชั่นสูงสุดที่เราสามารถทำได้หรือไม่?

ดังนั้นหากอินพุตเป็น [3,2,4,5,5] เอาต์พุตจะเป็น 4 เนื่องจากเราสามารถสร้างพาร์ติชั่นได้เช่น [3,2], [4], [5], [5]

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

  • cnt :=1

  • n :=ขนาดของ arr

  • กำหนดอาร์เรย์ maxOfLeft ขนาด n

  • กำหนดอาร์เรย์ minOfRight ขนาด n

  • maxOfLeft[0] :=arr[0]

  • สำหรับการเริ่มต้น i :=1 เมื่อฉัน

    • maxOfLeft[i] :=สูงสุดของ maxOfLeft[i - 1] และ arr[i]

  • minOfRight[n - 1] =arr[n - 1]

  • สำหรับการเริ่มต้น i :=n - 2 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -

    • minOfRight[i] :=ขั้นต่ำของ minOfRight[i + 1] และ arr[i]

  • สำหรับการเริ่มต้น i :=0 เมื่อ i

    • ถ้า minOfRight[i + 1]>=maxOfLeft[i] แล้ว −

      • (เพิ่มขึ้นอีก 1)

  • ส่งคืน cnt

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxChunksToSorted(vector<int>& arr) {
      int cnt = 1;
      int n = arr.size();
      vector<int> maxOfLeft(n);
      vector<int> minOfRight(n);
      maxOfLeft[0] = arr[0];
      for (int i = 1; i < n; i++)
         maxOfLeft[i] = max(maxOfLeft[i - 1], arr[i]);
         minOfRight[n - 1] = arr[n - 1];
      for (int i = n - 2; i >= 0; i--)
         minOfRight[i] = min(minOfRight[i + 1], arr[i]);
      for (int i = 0; i < n - 1; i++) {
         if (minOfRight[i + 1] >= maxOfLeft[i])
         cnt++;
      }
      return cnt;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,2,4,5,5};
   cout << (ob.maxChunksToSorted(v));
}

อินพุต

{3,2,4,5,5}

ผลลัพธ์

4