โปรแกรมที่จะลบรายการย่อยเพื่อให้ได้จำนวนองค์ประกอบที่เท่ากันด้านล่างและด้านบน k ใน C++

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกหมายเลขหนึ่ง k เราสามารถลบรายการย่อยออกจากรายการได้ไม่เกินครั้งเดียว เราต้องหาความยาวของรายการผลลัพธ์ที่ยาวที่สุดเพื่อให้จำนวนตัวเลขน้อยกว่า k และมากกว่า k อย่างเคร่งครัด

ดังนั้นหากอินพุตเป็น nums =[6, 10, 8, 9, 3, 5], k =6 ผลลัพธ์จะเป็น 5 ราวกับว่าเราลบรายการย่อย [9] เราจะได้ [6, 10, 8, 3, 5] และมีตัวเลขสองตัว [3, 5] ซึ่งน้อยกว่า 6 และสองตัว [10, 8] มากกว่า 6

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ v ที่มีขนาดเท่ากับ nums + 1 และเติมด้วย 0
• cnt :=0
• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ nums อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
  • ถ้า nums[i]
  • (เพิ่มขึ้น cnt โดย 1)
• มิฉะนั้นเมื่อ nums[i]> k แล้ว:
  • (ลดลงทีละ 1)
• v[i + 1] =cnt

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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