समान संख्या में तत्व 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 से बड़ी हैं।

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

• nums के आकार के समान + 1 का एक सरणी v परिभाषित करें और 0 से भरें
• cnt := 0
• i := 0 से आरंभ करें, जब i < nums का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें -
  • यदि nums[i] < k, तो:
    • (cnt को 1 से बढ़ाएं)
  • अन्यथा जब nums[i] > k, तो:
    • (cnt को 1 से घटाएं)
  • v[i + 1] = cnt
• यदि v का अंतिम तत्व 0 है, तो nums का आकार लौटाएं
  • delta := v का अंतिम तत्व
• एक मैप m परिभाषित करें
• ans := अनंत
• i := 1 से आरंभ करें, जब i <= v का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें -
  • यदि m[v[i] - v का अंतिम तत्व] 0 के बराबर नहीं है या (v[i] - v का अंतिम तत्व 0 के समान है), तो -
    • ans := ans और i - m[v[i] - v का अंतिम तत्व] का न्यूनतम
  • m[v[i]] := i
• यदि ans अनंत के समान है, तो -
  • 0 लौटाएं
• अन्यथा
  • nums का आकार लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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