35ms c++ solution with simple explanation


  • 0
    I

    35ms c++ solution, can use some clean up. the concept is to use hash tables to construct a two D array and keep updating properly.

    class AllOne
    {
    private:
    	struct row
    	{
    		int num;
    		unordered_set<string> strSet;
    	};
    	list<row> matrix; 
    	unordered_map<string, list<row>::iterator> hash; 
    
    public:
    	/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    	void inc(string key)
    	{
    		if (hash.find(key) == hash.end())
    		{
    			if (matrix.empty() || matrix.back().num != 1)
    			{
    				matrix.push_back({ 1, { key } }); 
    				auto newrow = --matrix.end();
    				hash[key] = newrow;	
    			}
    			else
    			{
    				auto newrow = --matrix.end(); 
    				newrow->strSet.insert(key); /
    				hash[key] = newrow; 
    			}
    		}
    		else
    		{
    			auto row = hash[key];
    			auto prevrow = row;
    
    			if (row == matrix.begin() || (--prevrow)->num != (row)->num + 1) 一行
    			{
    				matrix.insert(row, { (row)->num + 1, {key} }); 
    				prevrow = row;
    				prevrow--; 
    				row->strSet.erase(key); 
    				if (row->strSet.size() == 0) 
    					matrix.erase(row);
    				hash[key] = prevrow; //
    			}
    			else
    			{
    				prevrow = row; 
    				prevrow--;
    				prevrow->strSet.insert(key); 
    				row->strSet.erase(key); 
    				if (row->strSet.size() == 0)
    					matrix.erase(row);
    				hash[key] = prevrow; 
    			}
    		}
    	};
    
    	/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    	void dec(string key)
    	{
    		if (hash.find(key) == hash.end())
    			return;
    		if (hash[key]->num == 1) 
    		{
    			hash[key]->strSet.erase(key);
    			if (hash[key]->strSet.size() == 0)
    			{
    				matrix.erase(hash[key]); 
    			}
    			hash.erase(key);
    		}
    		else
    		{
    			auto row = hash[key];
    			auto nextrow = row;
    			nextrow++;
    			if (nextrow == matrix.end() || nextrow->num  != row->num - 1) 
    			{
    				matrix.insert(nextrow, { row->num - 1, {key} }); 
    				row->strSet.erase(key); 
    				if (row->strSet.size() == 0)
    				{
    					matrix.erase(row);
    				}
    				hash[key] = --nextrow;
    			}
    			else
    			{
    				nextrow->strSet.insert(key);
    				row->strSet.erase(key);
    				if (row->strSet.size() == 0)
    				{
    					matrix.erase(row);
    				}
    				hash[key] = nextrow;
    			}
    		}
    	}
    
    	/** Returns one of the keys with maximal value. */
    	string getMaxKey()
    	{
    		return matrix.size() != 0 ? *(matrix.front().strSet.begin()) : "";
    	}
    
    	/** Returns one of the keys with Minimal value. */
    	string getMinKey()
    	{
    		return matrix.size() != 0 ? *(matrix.back().strSet.begin()) : "";
    	}
    };
    

Log in to reply
 

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