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

Giả sử có danh sách số nums và một số k, ta có thể xóa tối đa một danh sách con từ danh sách. Ta phải tìm độ dài danh sách kết quả dài nhất sao cho số lượng phần tử nhỏ hơn k và lớn hơn k bằng 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, vì nếu xóa danh sách con [9] ta đượ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, ta làm theo các bước sau:

• Định nghĩa mảng v cùng kích thước nums + 1 điền 0
• cnt := 0
• với i := 0 đến kích thước nums - 1
  • nếu nums[i] < k: tăng cnt 1
  • ngược lại nếu nums[i] > k: giảm cnt 1
  • v[i+1] = cnt
• nếu phần tử cuối v là 0, trả về kích thước nums
  • delta := phần tử cuối v
• Định nghĩa một map m
• ans := vô cực
• với i := 1 đến kích thước v
  • nếu m[v[i] - v.back()] != 0 hoặc (v[i] - v.back() == 0), thì ans := min(ans, i - m[v[i] - v.back()])
  • m[v[i]] := i
• nếu ans bằng vô cực, trả về 0, ngược lại trả về kích thước nums - ans

Hãy xem 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);
    }
};

int main() {
    Solution ob;
    vector<int> v = {6, 10, 8, 9, 3, 5};
    int k = 6;
    cout << ob.solve(v, k);
    return 0;
}

Đầu vào

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

Đầu ra

5