Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Permutations II

Leetcode algorithms 第 47 题:Permutations II。

题目

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

解答

全排列问题,跟上一题类似,使用递归算法。每次从当前位置x及其后面的位置中选择一个数放到位置x上,然后递归处理后续位置,直到到达末尾为止。

但是注意这里不是所有x及其后面的数字都能够选择,因为可能这个数字已经选过了,再次选择会导致出现重复的结果,解决的办法是在每次选择之前先扫描一次看该数字是否在x之后自身位置之前是否已经出现过了,如果没有才可以进行选择。

具体代码如下:

class Solution {
public:
    bool exist(const vector<int> &cur, int st, int ed) //判断ed位置上的数字在[st, ed)是否出现过
    {
        for (int i = st; i < ed; i++)
            if (cur[i] == cur[ed]) 
                return true;
        return false;
    }
    void f(int x, vector<int> &cur, vector<vector<int>> &ans)
    { //当前位置,当前选择的排列,答案
        if (x == cur.size()) //到达末尾
        {
            ans.push_back(cur);
            return;
        }
        for (int i = x; i < cur.size(); i++) //选择x及其后面的数字
            if (!exist(cur, x, i)) //没有出现过的才能选择
            {
                swap(cur[x], cur[i]);
                f(x+1, cur, ans);
                swap(cur[x], cur[i]); //回溯
            }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int>> ans;
        f(0, num, ans);
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论