Ordered_Multiset C++ || log(N) TC|| Find by order PBDS Approach || Commented Code ||
Intuition\nWe can get any element from PBDS structure at log(N) complexity that will save us from TLE.\n Describe your first thoughts on how to solve this probl
# Intuition\nWe can get any element from PBDS structure at log(N) complexity that will save us from TLE.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(logN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#include <ext/pb_ds/assoc_container.hpp>\n#include <ext/pb_ds/tree_policy.hpp>\nusing namespace __gnu_pbds;\n\ntemplate<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;\n\n\ntemplate<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;\nclass MedianFinder {\npublic:\n    ordered_multiset<double> st; //Declaring Ordered_MULTISET \n    MedianFinder() {\n        st.clear(); //Clearing osms if there is any garbage\n    }\n    \n    void addNum(int num) {\n        int x = (double)num;//typecasting to double\n        st.insert(x);\n    }\n    \n    double findMedian() {\n        double x = (double)st.size();\n        int n = st.size();\n        if(n&1){//If odd len then simply extracting mid value\n            x/=2;\n            double k = (double)(*st.find_by_order(x));\n            return k;\n        }\n        x/=2; //If even len then adding m1 and m2 two mid elemts and printing their mean\n        double m1 = (double)(*st.find_by_order(x));\n        double m2 = (double)(*st.find_by_order(--x));\n        double sm = (double)(m1)+(double)m2;\n        double res = (double)sm/(double)2.00;\n        return res;\n    }\n};\n\n/**\n * Your MedianFinder object will be instantiated and called as such:\n * MedianFinder* obj = new MedianFinder();\n * obj->addNum(num);\n * double param_2 = obj->findMedian();\n */\n```
['C++']