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(constchar*) 인삼 형식은 상수 문자 바늘입니다.

class Solution {
public:
    vector Permutation(string str)
    {
        vector ret;
        if(str.size()==0) return ret; 
        Helper(str, 0,ret);
        
        unordered_set myset;// 
        ret = Helper2(ret,myset);
        return ret;
    }
    
    //fixed:[0:start-1]
    //result:[start:size()-1]
    void Helper(string str,int start,vector &ret)
    {
        if(start==str.size())//string::size() string::length() 。
        {
            ret.push_back(str);
            return;
        }
        //[start:size()-1] 
        for(int i =start ;i Helper2(vector ret,unordered_set &myset)
    {
        for(auto str:ret)
        {
            myset.insert(str);
        }
        vector rets;
        for(auto str:myset)
        {
            rets.push_back(str);
        }
        sort(rets.begin(),rets.end());
        return rets;
    }
};

 
법2.차례로 돌아가다.더 간단한 귀속.붉은색과 검은색 나무로 이루어진 set은 그 자체가 정렬된 질서정연한 집합이다.
디테일 return vector>(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> permuteUnique(vector& nums) {
        unordered_set> ret;
        if(nums.empty())
            return vector>();
        Helper(nums,0,ret); 
        return vector>(ret.begin(),ret.end());

    }

    void Helper(vector nums,int start,unordered_set> &ret)
    {
        if(start==nums.size())
        {
            ret.insert(nums);
            return;
        }
        for(int i=start;i

 
unordered_set 용기 중의 키는 무질서하기 때문에 상술한 증가 요구를 만족시키지 못하고, set는 용기 중의 키의 질서를 보장할 수 있다.
set는 질서를 유지할 수 있다. 왜냐하면 밑바닥은 RB-Tree, 천연의 질서 구조를 바탕으로 하고 unordered_set 밑바닥은hashtable입니다.
그때 unordered_를 썼던 기억이 나요.set가class나struct용기를 만들 때 특정한hash함수를 실현해야 한다. 원소가 적고hashbucket이 많을 때 부하인자가 적고 충돌할 확률이 적다. 이렇게 하면unordered_set의 검색 효율.따라서 부하 인자가 어떤 상수(1 또는 0.75)보다 크면 해시표를 확장해야 한다.
다음 테스트에서 set 및 unordered_set 구별

int main()
{
	sets1;
	unordered_sets2;
	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
더 많은 방법
다음으로 전송:https://www.cnblogs.com/lightmare/p/10463457.html