Chương trình xóa danh sách con để nhận cùng số phần tử bên dưới và bên trên k trong C ++

Giả sử chúng ta có một danh sách các số được gọi là num và một số khác k, chúng ta có thể loại bỏ bất kỳ danh sách con nào nhiều nhất một lần khỏi danh sách. Chúng ta phải tìm độ dài của danh sách kết quả dài nhất sao cho lượng số nhỏ hơn k và lớn hơn k là như nhau.

Vì vậy, nếu đầu vào là nums =[6, 10, 8, 9, 3, 5], k =6, thì đầu ra sẽ là 5, như nếu chúng ta loại bỏ danh sách con [9] thì chúng ta sẽ nhận được [6, 10, 8, 3, 5] và có hai số [3, 5] nhỏ hơn 6 và hai số [10, 8] lớn hơn 6.

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

• Xác định một mảng v có kích thước giống như nums + 1 và điền bằng 0
• cnt:=0
• để khởi tạo i:=0, khi tôi
• nếu nums [i]
• (tăng cnt lên 1)

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:
   int solve(vector<int>& nums, int k) {
      vector<int> v(nums.size() + 1, 0);
      int cnt = 0;
      for (int i = 0; i < nums.size(); ++i) {
         if (nums[i] < k)
            ++cnt;
         else if (nums[i] > k)
            --cnt;
         v[i + 1] = cnt;
      }
      if (v.back() == 0) return int(nums.size());
      int delta = v.back();
      map<int, int> m;
      int ans = INT_MAX;
      for (int i = 1; i <= v.size(); ++i) {
         if (m[v[i] - v.back()] != 0 || v[i] - v.back() == 0) {
            ans = min(ans, i - m[v[i] - v.back()]);
         }
         m[v[i]] = i;
      }
      if (ans == INT_MAX)
         return 0;
      else
         return int(nums.size() - ans);
   }
};
main(){
   Solution ob;
   vector<int> v = {6, 10, 8, 9, 3, 5};
   int k = 6;
   cout << ob.solve(v, k); }

Đầu vào

{6, 10, 8, 9, 3, 5}, 6

Đầu ra

5