C++ O(N*logK) using two std::set


  • 1
    B
        vector<double> medianSlidingWindow(vector<int>& nums, int k) {
            vector<double> res;
            multiset<int> st1, st2;
            for(int i=0;i<nums.size();i++) {
                if(i>=k) {
                    if(st1.count(nums[i-k])) st1.erase(st1.find(nums[i-k]));
                    else if(st2.count(nums[i-k])) st2.erase(st2.find(nums[i-k]));
                }
                if(st1.size()<=st2.size()) {
                    if(st2.empty() || nums[i]<=*st2.begin()) st1.insert(nums[i]);
                    else {
                        st1.insert(*st2.begin());
                        st2.erase(st2.begin());
                        st2.insert(nums[i]);
                    }
                }
                else {
                    if(nums[i]>=*st1.rbegin()) st2.insert(nums[i]);
                    else {
                        st2.insert(*st1.rbegin());
                        st1.erase(--st1.end());
                        st1.insert(nums[i]);
                    }                
                }
                if(i>=(k-1)) {
                    if(k%2) res.push_back(*st1.rbegin());
                    else res.push_back(((double)*st1.rbegin()+(double)*st2.begin())/2);
                }
            }
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.