c++, iterative solution, O(1) extra space, beats 92.94%


  • 0
    B

    Here's an iterative solution which only use O(1) extra space.The main idea is build the permutations for i first elements based on the permutations for i-1 first elements.The key problem of iterative solution is to avoid dumplicate.I do as follow:

    for every permutation of i-1 first elements,:
     we first add element i to tail of the permutation.
     then we compare element i with element in permutation from tail to head(except last element), if the element is not euqal to element i, we swap them and get an new permutation, else break;

    The principle is hard to say.I hope someone can expain.

    vector<vector<int>> permuteUnique(vector<int>& nums) {
    	vector<vector<int>> results;
    	if(nums.size() == 0)
    		return results;
    	sort(nums.begin(), nums.end());
    	int n = nums.size(), size;
    	vector<int> array;
    	results.push_back(vector<int>(n, nums[0]));
    	for(int i = 1; i < nums.size(); i++)
    	{
    		size = results.size();
    		for(int j = 0; j < size; j++)
    		{
    			results[j][i] = nums[i];
    			for(int k = i - 1; k >= 0; k--)
    			{
    				if(results[j][k] != nums[i])
    				{
    					results.push_back(results[j]);
    					results.back()[i] = results.back()[k];
    					results.back()[k] =  nums[i];
    				}
    				else
    					break;
    			}
    		}
    		
    	}
    	return results;
    }

Log in to reply
 

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