LRUCache Count Miss

给一个array, 给一个cache max size, 输出miss count。

• example：

  input array: [1，2，3，4，5，4，1]
  size: 4
  

  analysis

  1 miss
  2 miss
  3 miss
  4 miss
  5 miss  replace 1
  4 hit   move 4 to the head   
  1 miss  replace 2
  

  [1,2,3,4] -> [2,3,4,5] -> [2,3,5,4] -> [3,4,5,1]
  

Solution

class Solution {
  public:
    int countMiss(vector<int> input, int size) {
      unordered_map<int, int> map;
      priority_queue<pair<int, int> > minHeap;
      int n = input.size();
      int count = 0;
      for ( int i = 0; i < n; i++ ) {
        if ( map.find(input[i]) == map.end() and map.size() < size ) {
          // case of count
          map[input[i]] = i;
          minHeap.push(pair<int, int>(-i, input[i]));
          count += 1;
          continue;
        }
        if ( map.find(input[i]) != map.end() ) {
          // case of hit
          map[input[i]] = i; // will update in heap in later manipulation;
          continue;
        }
        while ( true ) {
          int j = -minHeap.top().first, val = minHeap.top().second;
          minHeap.pop();
          if ( map[val] != j ) minHeap.push(pair<int, int>(-map[val], val));
          else {
            map.erase(map.find(val));
            break;
          }
        }
        map[input[i]] = i;
        minHeap.push(pair<int, int>(-i, input[i]));
        count += 1;
      }
      return count;
    }
};

int main() {
  Solution sol;
  int arr[7] = {1,2,3,4,5,4,1};
  vector<int> input(arr, arr + sizeof(arr)/sizeof(arr[0]));
  int size = 5;
  int res = sol.countMiss(input, size);
  cout << res << endl;
  return 0;
}