程序删除子列表以在C ++中获得k以下和以上相同数量的元素

假设我们有一个称为nums和另一个数字k的数字列表，我们最多可以从列表中删除任何子列表一次。我们必须找到最长的结果列表的长度，以使严格小于k和严格大于k的数字量相同。

因此，如果输入类似于nums = [6、10、8、9、3、5]，k = 6，则输出将为5，就像我们删除子列表[9]一样，则得到[6， 10、8、3、5]，并且有两个小于3的数字[3、5]和两个大于6的数字[10、8]。

为了解决这个问题，我们将遵循以下步骤-

• 定义大小为nums + 1的数组v并用0填充

• cnt：= 0

• 对于初始化i：= 0，当i <nums大小时，更新（将i增加1），执行-

• （将cnt减1）

• （将cnt增加1）

• 如果nums [i] <k，则：

• 否则，当nums [i]> k时：

• v [i + 1] = cnt

• 如果v的最后一个元素为0，则返回nums的大小

• delta：= v的最后一个元素

• 定义一张映射

• ans：=无限

• 对于初始化i：= 1，当i <= v的大小时，更新（将i增加1），-

• ans：= ans和i的最小值-m [v [i]-v的最后一个元素]

• 如果m [v [i]-v的最后一个元素不等于0或（v [i]-v的最后一个元素等于0），则-

• m [v [i]]：= i

• 如果ans与无穷大相同，则-

• 返回0

• 除此以外

• 返回的数字大小

让我们看下面的实现以更好地理解-

示例

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

输入值

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

输出结果

5