Computer >> Máy Tính >  >> Lập trình >> C ++

Mảng phân vùng thành các khoảng riêng biệt trong C ++

Giả sử chúng ta có một mảng A, chúng ta phải phân vùng nó thành hai mảng con trái và phải sao cho -

  • Mọi phần tử trong mảng con bên trái nhỏ hơn hoặc bằng mọi phần tử trong mảng con bên phải.

  • mảng con bên trái và bên phải không trống.

  • mảng con bên trái có kích thước nhỏ nhất có thể.

Chúng ta phải tìm chiều dài bên trái sau khi phân vùng như vậy. Nó được đảm bảo rằng một phân vùng như vậy tồn tại.

Vì vậy, nếu đầu vào là [5,0,3,8,6], thì đầu ra sẽ là 3, vì mảng bên trái sẽ là [5,0,3] và mảng con bên phải sẽ là [8,6].

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

  • n:=kích thước của A, tạo một mảng maxx có kích thước n

  • minVal:=phần tử cuối cùng của A

  • maxx [0]:=A [0]

  • cho tôi trong phạm vi từ 1 đến n - 1

    • maxx [i]:=max of A [i] và A [i - 1]

  • ans:=kích thước của A - 1

  • đối với tôi trong phạm vi n - 1 xuống 1

    • minVal:=tối thiểu của minVal và A [i]

    • nếu minVal> =max [i - 1], thì ans:=i

  • trả lại ans

Ví dụ

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

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

Đầu vào 

[5,0,3,8,6]

Đầu ra 

3