C++ 4 ms one-pass with constant space


  • 0
    P
    void sortColors(vector<int>& nums)
    {
    	const int unknown = 888888;
    	vector<int> colorsPos = { unknown, unknown, unknown };
    
    	int numsLen = nums.size();
    	for (int i = 0; i < numsLen; ++i)
    	{
    		int color = nums[i];
    		if (colorsPos[color] == unknown)
    			colorsPos[color] = i;
    
    		for (int nextColor = color + 1; nextColor < colorsPos.size(); ++nextColor)
    		{
    			if (colorsPos[color] == unknown || colorsPos[nextColor] == unknown)
    			{
    				continue;
    			}
    			int nextColPos = colorsPos[nextColor];
    			if (i > nextColPos)
    			{
    				nums[i] = nextColor;
    				++colorsPos[nextColor];
    				nums[nextColPos] = color;
    				colorsPos[color] = min(colorsPos[color], nextColPos);
    				color = nextColor;
    			}
    		}
    	}
    }

Log in to reply
 

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