16 ms c++ solution, very simple idea, no recursion.


  • -1

    At first, sort numbers into ascending order. Then use the idea of "Next Permutation", find the next permutation and next, next.... For example "2,1,3", -> 123 -> 132->..., until 321 that there is no number smaller than it's right side number.

    Here is the code:

    vector<vector<int>> permute(vector<int>& s) 
    {
    	vector<vector<int>> res;;
    	const int sz = s.size();
    	if (sz <= 1)
    	{
    		res.push_back(s);
    		return res;
    	}
    	sort(s.begin(), s.end());//先对数列进行排序
    	res.push_back(s);
    	int le;
    	int ri;
    	int cur;
    	int t;
    	while (1)
    	{
    		le = 0;
    		ri = sz - 1;
    		for (; ri > 0; --ri)
    		{
    			if (s[ri - 1] < s[ri])
    				break;
    		}
    		if (ri <= 0)//Already become a descending order, return. 
    		{
    			return res;
    		}
    		cur = ri - 1;
    		le = ri;
    		ri = sz - 1;
    		for (; ri >= le && s[ri] <= s[cur]; --ri);
    		if (ri - cur)
    		{
    			t = s[ri];
    			s[ri] = s[cur];
    			s[cur] = t;
    		}
    		sort(s.begin() + cur+1, s.end());
    		res.push_back(s);
    	}
    	return res;
    }

  • 0

    PS: This solution can be used to solve "Permutations II".


Log in to reply
 

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