[LeetCode]All O`one Data Structure

我们用类似LFU Cache的design即可，区别是我们不需要evict element，inc的操作就和LFU Cache put的操作一样。dec的操作也是类似的。时间复杂度都是常数时间，我们用c++自带的list来实现，这样可以简化我们的代码，代码如下：

	struct NodeList
	{
	int count;
	list<string> strs;
	NodeList(string key, int c) : count(c), strs({key})
	{
	}
	};
	class AllOne {
	public:
	/** Initialize your data structure here. */
	AllOne() {
	}
	/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
	void inc(string key) {
	if(m_map.find(key) == m_map.end())
	{
	if(m_matrix.empty() || m_matrix.front().count != 1)
	{
	auto iter = m_matrix.emplace(m_matrix.begin(), key, 1);
	m_map[key] = make_pair(iter, iter->strs.begin());
	}
	else
	{
	auto row = m_matrix.begin();
	row->strs.emplace_front(key);
	m_map[key] = make_pair(row, row->strs.begin());
	}
	}
	else
	{
	auto row = m_map[key].first;
	auto col = m_map[key].second;
	auto next = row;
	++next;
	if(next != m_matrix.end() && next->count == row->count + 1)
	{
	next->strs.emplace_front(key);
	m_map[key] = make_pair(next, next->strs.begin());
	}
	else
	{
	auto iter = m_matrix.emplace(next, key, row->count + 1);
	m_map[key] = make_pair(iter, iter->strs.begin());
	}
	row->strs.erase(col);
	if(row->strs.empty())m_matrix.erase(row);
	}
	}
	/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
	void dec(string key) {
	if(m_map.find(key) == m_map.end())return;
	auto row = m_map[key].first;
	auto col = m_map[key].second;
	if(row->count == 1)
	{
	row->strs.erase(col);
	if(row->strs.empty())m_matrix.erase(row);
	m_map.erase(key);
	return;
	}
	auto prev = row;
	--prev;
	if(row != m_matrix.begin() && prev->count == row->count - 1)
	{
	prev->strs.emplace_front(key);
	m_map[key] = make_pair(prev, prev->strs.begin());
	}
	else
	{
	auto iter = m_matrix.emplace(row, key, row->count - 1);
	m_map[key] = make_pair(iter, iter->strs.begin());
	}
	row->strs.erase(col);
	if(row->strs.empty())m_matrix.erase(row);
	}
	/** Returns one of the keys with maximal value. */
	string getMaxKey() {
	return m_matrix.empty()? "": m_matrix.back().strs.front();
	}
	/** Returns one of the keys with Minimal value. */
	string getMinKey() {
	return m_matrix.empty()? "":m_matrix.front().strs.front();
	}
	private:
	list<NodeList> m_matrix;
	unordered_map<string, pair<list<NodeList>::iterator, list<string>::iterator>> m_map;
	};
	/**
	* Your AllOne object will be instantiated and called as such:
	* AllOne obj = new AllOne();
	* obj.inc(key);
	* obj.dec(key);
	* string param_3 = obj.getMaxKey();
	* string param_4 = obj.getMinKey();
	*/

view raw All O`one Data Structure.cpp hosted with ❤ by GitHub