C++ में k के नीचे और ऊपर के तत्वों की समान संख्या प्राप्त करने के लिए सबलिस्ट को हटाने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे nums और दूसरी संख्या k कहा जाता है, हम किसी भी सबलिस्ट को सूची से अधिकतम एक बार हटा सकते हैं। हमें सबसे लंबी परिणामी सूची की लंबाई का पता लगाना होगा जैसे कि k से सख्ती से कम और k से सख्ती से बड़ी संख्या समान हो।

इसलिए, यदि इनपुट संख्या =[6, 10, 8, 9, 3, 5], k =6 की तरह है, तो आउटपुट 5 होगा, जैसे कि हम सबलिस्ट [9] को हटा दें तो हमें [6, 10, 8, 3, 5] और दो संख्याएँ [3, 5] हैं जो 6 से छोटी हैं और दो संख्याएँ [10, 8] 6 से बड़ी हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• संख्या + 1 के समान आकार की एक सरणी v परिभाषित करें और 0 से भरें
• सीएनटी:=0
• इनिशियलाइज़ i :=0 के लिए, जब i <अंकों का आकार, अपडेट करें (i से 1 बढ़ाएँ), करें -
  • यदि अंक [i]
  • (cnt 1 से बढ़ाएँ)
• अन्यथा जब nums[i]> k, तब:
  • (cnt 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