Danh sách tách trong C ++

Giả sử chúng ta có một danh sách các số nguyên được gọi là nums, chúng ta phải tìm xem liệu chúng ta có thể phân vùng danh sách thành hai danh sách con (không trống) sao cho mọi số ở phần bên trái đều nhỏ hơn không hơn mọi số ở phần bên phải.

Vì vậy, nếu đầu vào là [6,4,3,8,10], thì đầu ra sẽ là true, là left =[6,4,3] và right =[8,10]

Để 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 nums

• Xác định quyền mảng có kích thước n

• Xác định một mảng bên trái có kích thước n

• left [0]:=nums [0]

• phần tử cuối cùng của bên phải:=phần tử cuối cùng của nums

• để khởi tạo i:=1, khi i

  • left [i]:=tối đa left [i - 1] và nums [i]

• để khởi tạo i:=n - 2, khi i> =0, cập nhật (giảm i đi 1), thực hiện -

  • right [i]:=tối thiểu bên phải [i + 1] và nums [i]

• để khởi tạo i:=0, khi tôi

  • nếu trái [i]

    • trả về true

• trả về false

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 solve(vector<int> &nums) {
      int n = nums.size();
      vector<int> right(n);
      vector<int> left(n);
      left[0] = nums[0];
      right.back() = nums.back();
      for (int i = 1; i < n; i++) {
         left[i] = max(left[i - 1], nums[i]);
      }
      for (int i = n - 2; i >= 0; i--) {
         right[i] = min(right[i + 1], nums[i]);
      }
      for (int i = 0; i < n - 1; i++) {
         if (left[i] < right[i + 1])
         return true;
      }
      return false;
   }
};
main() {
   Solution ob;
   vector<int> v = {6,4,3,8,10};
   cout << (ob.solve(v));
}

Đầu vào

{6,4,3,8,10}

Đầu ra

1