LeetCode47.Permutations II（剑指offer38-1)

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

Example:

Input: [1,1,2]

Output:

[

  [1,1,2],

  [1,2,1],

  [2,1,1]

]

法1.递归。swap.回溯。唯一要多做的就是去重。用unordered_set的insert就行。因为用的是hash的无序集合，所以要用std::sort重排一下。

细节：string 的长度 .size()或者.length()都是一样的。

而strlen(const char *) 形参类型是常量字符指针。

class Solution {

public:

    vector<string> Permutation(string str)

    {

        vector<string> ret;

        if(str.size()==0) return ret;

        Helper(str, 0,ret);

        unordered_set<string> myset;//去重

        ret = Helper2(ret,myset);

        return ret;

    }

    //fixed:[0:start-1]

    //result:[start:size()-1]

    void Helper(string str,int start,vector<string> &ret)

    {

        if(start==str.size())//string::size()和string::length()一样的。

        {

            ret.push_back(str);

            return;

        }

        //[start:size()-1]全排列

        for(int i =start ;i<str.size();i++)//

        {

            swap(str[i],str[start]);

            Helper(str, start+1,ret);

            swap(str[i],str[start]);

        }

    }

    vector<string> Helper2(vector<string> ret,unordered_set<string> &myset)

    {

        for(auto str:ret)

        {

            myset.insert(str);

        }

        vector<string> rets;

        for(auto str:myset)

        {

            rets.push_back(str);

        }

        sort(rets.begin(),rets.end());

        return rets;

    }

};

法2.递归。更简单的递归。用红黑树实现的set，是本身就已经排序好的有序集合。

细节。 return vector<vector<int>>(ret.begin(),ret.end());这种写法是对的。在leetcode里面只能用有序集合。否则用unordered_set报错：需要实现特定的hash函数。

error: static assertion failed: hash function must be invocable with an argument of key type

class Solution {

public:

    vector<vector<int>> permuteUnique(vector<int>& nums) {

        unordered_set<vector<int>> ret;

        if(nums.empty())

            return vector<vector<int>>();

        Helper(nums,0,ret);

        return vector<vector<int>>(ret.begin(),ret.end());

    }

    void Helper(vector<int> nums,int start,unordered_set<vector<int>> &ret)

    {

        if(start==nums.size())

        {

            ret.insert(nums);

            return;

        }

        for(int i=start;i<nums.size();i++)

        {

            swap(nums[i],nums[start]);

            Helper(nums,start+1,ret);

            swap(nums[i],nums[start]);

        }

    }

};

unordered_set容器中的key是无序的，就不满足上述递增要求了，而set能保证容器中key有序。

set能保持有序，因为底层基于RB-Tree，天然的有序结构，而unordered_set底层则是hashtable。

记得当时用unordered_set做class或者struct的容器时就得实现特定的hash函数，当元素较少、hash bucket很多的时候，负载因子很小，发生冲突的概率很小，这样保证了unordered_set的查找效率。因此，在负载因子大于某个常数（1或者0.75）就需要对哈希表进行扩容。

下面一个测试看出在使用上set和unordered_set区别

int main()

{

	set<int>s1;

	unordered_set<int>s2;

	s1.insert(4);

	s1.insert(2);

	s1.insert(3);

	s1.insert(1);

	s2.insert(4);

	s2.insert(2);

	s2.insert(3);

	s2.insert(1);

	for (auto it = s1.begin(); it != s1.end(); ++it)

		cout << *it << " ";

	cout << endl;

	for (auto it = s2.begin(); it != s2.end(); ++it)

		cout << *it << " ";

	cout << endl;

}

输出：

1 2 3 4

4 2 3 1

更多做法

巴特西

LeetCode47.Permutations II（剑指offer38-1)

最新文章

热门文章