Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सभी विषम लंबाई वाली सबलिस्ट्स के माध्यिका का योग ढूंढने का प्रोग्राम


परिचय

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, हमें दी गई सूची की हर विषम-लंबाई (odd-length) वाली सबलिस्ट के माध्यिका (medians) का योग ढूंढना है।

तो, यदि इनपुट nums = [2, 4, 6, 3] है, तो आउटपुट 23 होगा, क्योंकि विषम-लंबाई वाली सबलिस्ट्स हैं: [2], [4], [6], [3], [2, 4, 6], [4, 6, 3], तो माध्यिका का योग 2 + 4 + 6 + 3 + 4 + 4 = 23 है।

समाधान दृष्टिकोण

दो हीप्स (मैक्स-हीप और मिन-हीप) का उपयोग करके प्रत्येक सबअरे के लिए रनिंग माध्यिका बनाए रखें। प्रत्येक प्रारंभिक इंडेक्स i के लिए, j को i से n-1 तक बढ़ाएं, हीप्स में एलिमेंट जोड़ें, उन्हें बैलेंस करें, और जब सबअरे लंबाई विषम हो (i%2 == j%2) तो माध्यिका को उत्तर में जोड़ें।

उदाहरण कोड

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int>& nums) {
    int ret = 0;
    for (int i = 0; i < nums.size(); i++) {
        priority_queue<int> que_max;  // मैक्स हीप
        priority_queue<int, vector<int>, greater<int>> que_min;  // मिन हीप
        for (int j = i; j < nums.size(); j++) {
            que_max.push(nums[j]);
            while (que_max.size() - que_min.size() >= 2) {
                que_min.push(que_max.top());
                que_max.pop();
            }
            while (que_min.size() && que_max.top() > que_min.top()) {
                int a = que_max.top(); que_max.pop();
                int b = que_min.top(); que_min.pop();
                que_max.push(b);
                que_min.push(a);
            }
            if (i % 2 == j % 2) {
                ret += que_max.top();
            }
        }
    }
    return ret;
}

int main(){
    vector<int> v = {2, 4, 6, 3};
    cout << solve(v);
    return 0;
}

इनपुट

{2, 4, 6, 3}

आउटपुट

23

व्याख्या

सबलिस्ट्स और उनकी माध्यिका: [2]→2, [4]→4, [6]→6, [3]→3, [2,4,6]→4, [4,6,3]→4 योग = 2+4+6+3+4+4 = 23

निष्कर्ष

दो हीप्स दृष्टिकोण प्रत्येक सबअरे के लिए O(log n) में माध्यिका बनाए रखता है। कुल समय जटिलता O(n² log n) है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।


  1. C++ प्रोग्राम किसी संख्या के विषम गुणनखंडों का योग ज्ञात करने के लिए C++ प्रोग्राम किसी संख्या के विषम गुणनखंडों का योग ज्ञात करने के लिए

    एक धनात्मक पूर्णांक दिया गया है और कार्य उस संख्या के विषम गुणनखंडों को उत्पन्न करना और दिए गए विषम गुणनखंडों का योग निकालना है। उदाहरण इनपुट: संख्या = 20 आउटपुट: विषम गुणनखंडों का योग है: 6 इनपुट: संख्या = 18 आउटपुट: विषम गुणनखंडों का योग है: 13 तो, परिणाम = 1 + 5 = 6 नीचे दिए गए प्रोग्राम में

  1. - Python में सभी विषम लंबाई वाले सबएरे का योग खोजने का प्रोग्राम

    मान लीजिए हमारे पास nums नामक धनात्मक मानों की एक सरणी है, हमें सभी संभावित विषम-लंबाई वाले सबएरे का योग ढूंढना है। जैसा कि हम जानते हैं एक सबएरे सरणी का एक सन्निकट उपअनुक्रम है। हमें nums के सभी विषम-लंबाई वाले सबएरे का योग ढूंढना है। इसलिए, यदि इनपुट है: nums = [3,8,2,5,7], तो आउटपुट होगा: विषम-ल

  1. - पायथन में सभी सन्निकट सबलिस्ट के योग का योग खोजने का प्रोग्राम

    मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, अब हर सन्निकट सबअरे पर विचार करें। इनमें से प्रत्येक सबअरे का योग करें और इन सभी मानों का योग लौटाएं। अंत में, परिणाम को 10**9 + 7 से मोड करें। उदाहरण के लिए, यदि इनपुट है nums = [3, 4, 6], तो आउटपुट होगा 43, क्योंकि हमारे पास निम्नलिखित सबअरे ह