sliding window medium
data stream median的follow up。要用哈希堆做定点删除。
code
class node {
public:
int idx;
int num;
node(int idx = 0, int num = 0)
{
this->idx = idx;
this->num = num;
}
};
class hashheap {
public:
vector<int> heap;
unordered_map<int, node> hash;
int count;
int mode;
hashheap(int mode)
{
this->mode = mode;
this->count = 0;
}
int size()
{
return count;
}
bool isEmpty()
{
return count == 0;
}
int top()
{
return heap[0];
}
int parent(int id)
{
if(id == 0)
{
return -1;
}
return (id-1)/2;
}
int lson(int id)
{
return id*2+1;
}
int rson(int id)
{
return id*2+2;
}
int comparesmall(int a, int b)
{
if(a <= b)
{
if(mode == 0)
{
return true;
}
else
{
return false;
}
}
else
{
if(mode == 0)
{
return false;
}
else
{
return true;
}
}
}
void swap(int ida, int idb)
{
int valuea = heap[ida];
int valueb = heap[idb];
int numa = hash[valuea].num;
int numb = hash[valueb].num;
hash[valuea] = node(idb, numa);
hash[valueb] = node(ida, numb);
heap[ida] = valueb;
heap[idb] = valuea;
}
/*
void siftup(int id)
{
while(parent(id) != -1)
{
int pid = parent(id);
if(comparesmall(heap[pid], heap[id]) == true)
{
break;
}
else
{
swap(id, pid);
}
id = pid;
}
}
void siftdown(int id)
{
while(lson(id) < heap.size())
{
int leftid = lson(id);
int rightid = rson(id);
int son;
if(rightid >= heap.size() || comparesmall(heap[leftid], heap[rightid]) == true)
{
son = leftid;
}
else
{
son = rightid;
}
if(comparesmall(heap[id], heap[son]))
{
break;
}
else
{
swap(id, son);
}
id = son;
}
}
*/
void siftup(int id)
{
while(parent(id) != -1)
{
int p = parent(id);
if(comparesmall(heap[p], heap[id]) == true)
{
break;
}
else
{
swap(id, p);
}
id = p;
}
}
void siftdown(int id)
{
while(lson(id) < heap.size())
{
int leftid = lson(id);
int rightid = rson(id);
int son;
if(rightid >= heap.size() || comparesmall(heap[leftid], heap[rightid]) == true)
{
son = leftid;
}
else
{
son = rightid;
}
if(comparesmall(heap[id], heap[son]))
{
break;
}
else
{
swap(id, son);
}
id = son;
}
}
int pop()
{
if(count == 0)
{
return 0;
}
count--;
int now = heap[0];
node hashnow = hash[now];
if(hashnow.num > 1)
{
hash[now] = node(0, hashnow.num-1);
}
else
{
swap(0, heap.size()-1);
hash.erase(now);
heap.pop_back();
if(heap.size() > 0)
{
siftdown(0);
}
}
return now;
}
void add(int now)
{
count++;
if(hash.find(now) != hash.end())
{
node hashnow = hash[now];
hash[now] = node(hashnow.idx, hashnow.num+1);
}
else
{
heap.push_back(now);
hash[now] = node(heap.size()-1, 1);
siftup(heap.size()-1);
}
}
void remove(int now)
{
count--;
node hashnow = hash[now];
int id = hashnow.idx;
// more than 1
if(hashnow.num > 1)
{
hash[now] = node(hashnow.idx, hashnow.num-1);
return ;
}
// just 1
swap(hashnow.idx, heap.size()-1);
hash.erase(now);
heap.pop_back();
if(heap.size() > hashnow.idx)
{
siftup(id);
siftdown(id);
}
}
/*
void add(int value)
{
count++;
if(hash.find(value) != hash.end())
{
hash[value].num++;
}
else
{
int idx = heap.size();
heap.push_back(value);
hash[value] = node(idx, 1);
siftup(idx);
}
}
int pop()
{
if(count == 0)
{
return 0;
}
count--;
int now = heap[0];
if(hash[now].num > 1)
{
hash[now].num--;
}
else
{
swap(0, heap.size()-1);
heap.pop_back();
hash.erase(now);
if(heap.size() > 0)
{
siftdown(0);
}
}
return now;
}
void remove(int now)
{
count--;
if(hash[now].num > 1)
{
hash[now].num--;
}
else
{
int idx = hash[now].idx;
swap(idx, heap.size()-1);
heap.pop_back();
hash.erase(now);
if(heap.size() > idx)
{
siftup(idx);
siftdown(idx);
}
}
}*/
};
/*
class Node {
public:
int idx;
int num;
Node(int idx = 0, int num = 0)
{
this->idx = idx;
this->num = num;
}
};
class hashheap {
public:
vector<int> heap;
int mode; // 0 --> minheap, 1 --> maxheap
int count;
unordered_map<int, Node> hash;
hashheap(int mode)
{
this->mode = mode;
this->count = 0;
}
int top()
{
return heap[0];
}
int size()
{
return count;
}
bool empty()
{
return count == 0;
}
int parent(int id)
{
if(id == 0)
{
return -1;
}
return (id-1)/2;
}
int lson(int id)
{
return id*2+1;
}
int rson(int id)
{
return id*2+2;
}
bool comparesmall(int a, int b)
{
if(a <= b)
{
if(mode == 0)
{
return true;
}
else
{
return false;
}
}
else
{
if(mode == 0)
{
return false;
}
else
{
return true;
}
}
}
void swap(int ida, int idb)
{
int valA = heap[ida];
int valB = heap[idb];
int numA = hash[valA].num;
int numB = hash[valB].num;
hash[valA] = Node(idb, numA);
hash[valB] = Node(ida, numB);
heap[ida] = valB;
heap[idb] = valA;
}
int pop()
{
if(count == 0)
{
return 0;
}
count--;
int now = heap[0];
Node hashnow = hash[now];
if(hashnow.num > 1)
{
hash[now] = Node(0, hashnow.num-1);
}
else
{
swap(0, heap.size()-1);
hash.erase(now);
heap.pop_back();
if(heap.size() > 0)
{
siftdown(0);
}
}
return now;
}
void add(int now)
{
count++;
if(hash.find(now) != hash.end())
{
Node hashnow = hash[now];
hash[now] = Node(hashnow.idx, hashnow.num+1);
}
else
{
heap.push_back(now);
hash[now] = Node(heap.size()-1, 1);
siftup(heap.size()-1);
}
}
void remove(int now)
{
count--;
Node hashnow = hash[now];
int id = hashnow.idx;
// more than 1
if(hashnow.num > 1)
{
hash[now] = Node(hashnow.idx, hashnow.num-1);
return ;
}
// just 1
swap(hashnow.idx, heap.size()-1);
hash.erase(now);
heap.pop_back();
if(heap.size() > hashnow.idx)
{
siftup(id);
siftdown(id);
}
}
void siftup(int id)
{
while(parent(id) != -1)
{
int pid = parent(id);
if(comparesmall(heap[pid], heap[id]) == true)
{
break;
}
else
{
swap(id, pid);
}
id = pid;
}
}
void siftdown(int id)
{
while(lson(id) < heap.size())
{
int leftid = lson(id);
int rightid = rson(id);
int son;
if(rightid >= heap.size() || comparesmall(heap[leftid], heap[rightid]) == true)
{
son = leftid;
}
else
{
son = rightid;
}
if(comparesmall(heap[id], heap[son]))
{
break;
}
else
{
swap(id, son);
}
id = son;
}
}
};*/
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: The median of the element inside the window at each moving
*/
vector<int> medianSlidingWindow(vector<int> &nums, int k) {
// write your code here
vector<int> ret;
if(nums.size() == 0)
{
return ret;
}
int median = nums[0];
hashheap left(1);
hashheap right(0);
for(int i = 0; i<nums.size(); i++)
{
if(i != 0)
{
if(nums[i] < median)
{
left.add(nums[i]);
}
else
{
right.add(nums[i]);
}
}
if(i >= k)
{
int del = nums[i-k];
if(median == del)
{
if(left.size() > 0)
{
median = left.pop();
}
else if(right.size() > 0)
{
median = right.pop();
}
}
else if(del < median)
{
left.remove(del);
}
else
{
right.remove(del);
}
}
while(right.size() - left.size() > 1)
{
left.add(median);
median = right.pop();
}
while(left.size() - right.size() > 0)
{
right.add(median);
median = left.pop();
}
if(i+1 >= k)
{
ret.push_back(median);
}
}
return ret;
/*
vector<int> ret;
if(nums.size() == 0)
{
return ret;
}
int median = nums[0];
hashheap left(1);
hashheap right(0);
for(int i = 0; i < nums.size(); i++)
{
// insert to two heap
if(i != 0)
{
if(nums[i] > median)
{
right.add(nums[i]);
}
else
{
left.add(nums[i]);
}
}
// remove elements
if(i >= k)
{
if(median == nums[i-k])
{
if(left.size() > 0)
{
median = left.pop();
}
else if(right.size() > 0)
{
median = right.pop();
}
}
else if(median < nums[i - k])
{
right.remove(nums[i-k]);
}
else
{
left.remove(nums[i-k]);
}
}
// adjust two heap
while(left.size() > right.size())
{
right.add(median);
median = left.pop();
}
while(right.size() > left.size() + 1)
{
left.add(median);
median = right.pop();
}
// output
if(i + 1 >= k)
{
ret.push_back(median);
}
}
return ret;
*/
}
};