【Lintcode】LRU Cache, Data Stream Median

주로 priorityqueue 의 용법
하 나 는 내 장 된 형식 우선 대기 열 입 니 다. 작은 루트 더 미 를 어떻게 설정 합 니까?
사용자 정의 데이터 구조 라면, 두 가지 방법 이 있다.
1. 이러한 데이터 구조의 비교 기 호 를 정의 하면 내 장 된 유형 으로 정리 할 수 있다.
2. 다시 불 러 오기 () 클래스 를 입력 합 니 다. 번호 보다 작 을 때 기본 값 은 큰 루트 입 니 다. 들 어 가 는 것 이 callable object 일 수도 있 습 니 다. 함수 가 안 될 것 같 습 니 다. 모 르 겠 습 니 다. 모 르 겠 습 니 다. 모 르 겠 습 니 다. 모 르 겠 습 니 다. 모 르 겠 습 니 다.
LRU Cache

class LRUCache{
public:
    // @param capacity, an integer
    
    int Time;
    typedef int key;
    typedef int time;
    typedef int value;
    typedef pair<key,time> ktpair;
    
    struct cmp
    {
        bool operator()(ktpair x1,ktpair x2)
        {
            return x1.second > x2.second;
        }
    };
    
    map<key,value> kv;
    map<key,time> kt;
    priority_queue<ktpair,vector<ktpair>,cmp> q;
    int Cap;
    
    LRUCache(int capacity) {
        // write your code here
        Time = 0;
        Cap = capacity;
    }
    
    void insert(int key,int value,int time)
    {
        kv[key] = value;
        kt[key] = time;
        q.push(make_pair(key,time));
    }
    
    // @return an integer
    int get(int key) {
        // write your code here
        Time++;
        value ret;
        if (kv.find(key) != kv.end())
        {
            int value = kv[key];
            insert(key,value,Time);
            return value;
        }
        else return -1;
    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    void set(int key, int value) {
        // write your code here
        Time++;
        if (kv.find(key) == kv.end())
        {
            insert(key,value,Time);
            if (!Cap)
            {
                for(;;)
                {
                    auto x = q.top();
                    auto ckey = x.first;
                    auto ctime = x.second;
                    q.pop();
                    if (kt.find(ckey) == kt.end() || kt[ckey] != ctime) continue;
                    else
                    {
                        kv.erase(ckey);
                        kt.erase(ckey);
                        break;
                    }
                }
            }
            else Cap--;
        }
        else insert(key,value,Time);
    }
};

Data Stream Median

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The median of numbers
     */
    vector<int> medianII(vector<int> &nums) {
        // write your code here
        priority_queue<int,vector<int>,less<int>> q1;
        priority_queue<int,vector<int>,greater<int>> q2;
        vector<int> ret;
        q1.push(INT_MIN);
        q2.push(INT_MAX);
        for (auto x : nums)
        {
            if (x < q2.top()) q1.push(x);
            else q2.push(x);
            if (q1.size() < q2.size())
            {
                q1.push(q2.top());
                q2.pop();
            }
            if (q1.size() > 1 + q2.size())
            {
                q2.push(q1.top());
                q1.pop();
            }
            ret.push_back(q1.top());
        }
        return ret;
    }
};