Permutations Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. 求數組元素的全排列,數組不含重復元素 算法1:遞歸 類似於DFS的遞歸. 對於包含n個元素的數組,先確定第一位置的元素，第一個位置有n中可能(每次把後面的元素和第一個元素交換)，然後求子數組[2…n]的全排列。由於一個數列的總共有n！個排列，因此時間復雜度為O（n！） class Solution { public: vector<vector<int> > permute(vector<int> &num) { vector<vector<int> > res; if(num.size() == 0)return res; vector<int> tmpres; permuteRecur(num, 0, res, tmpres); return res; } void permuteRecur(vector<int> &num, int index, vector<vector<int> >&res, vector<int>&tmpres) { if(index == num.size()) { res.push_back(tmpres); return; } for(int i = index; i < num.size(); i++) { swap(num[index], num[i]); tmpres.push_back(num[index]); permuteRecur(num, index+1, res, tmpres); tmpres.pop_back(); swap(num[index], num[i]); } } }; 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]. 求數組元素的全排列,數組含重復元素 分析：要避免重復，就要保證我們枚舉某個位置的元素時，不能枚舉重復。 算法2： 在算法1的基礎上，當我們枚舉第i個位置的元素時，若要把後面第j個元素和i交換，則先要保證[i…j-1]范圍內沒有和位置j相同的元素。有以下兩種做法（1）可以每次在需要交換時進行順序查找；（2）用哈希表來查重。具體見下面的代碼。 注意不要誤以為以下兩種做法能夠去重：（1）最開始先對數組進行排序，以後每次交換時，只要保證當前要交換的元素和前一個元素不同，這種做法是錯誤的，雖然開始進行了排序，但是元素的交換會使數組再次變的無序（2）每次進入遞歸函數permuteRecur時，對從當前索引開始的子數組排序，這種做法也是錯誤的，因為每次交換元素後，我們要恢復交換的元素，如果在遞歸函數內排序，就不能正確的恢復交換的元素。 本文地址 class Solution { public: vector<vector<int> > permuteUnique(vector<int> &num) { vector<vector<int> > res; if(num.size() == 0)return res; vector<int> tmpres; permuteRecur(num, 0, res, tmpres); return res; } void permuteRecur(vector<int> &num, int index, vector<vector<int> >&res, vector<int>&tmpres) { if(index == num.size()) { res.push_back(tmpres); return; } for(int i = index; i < num.size(); i++) if(i == index || !find(num, index, i, num[i])) { swap(num[index], num[i]); tmpres.push_back(num[index]); permuteRecur(num, index+1, res, tmpres); tmpres.pop_back(); swap(num[index], num[i]); } } //從數組的[start,end）范圍內尋找元素target bool find(vector<int> &num, int start, int end, int target) { for(int i = start; i < end; i++) if(num[i] == target) return true; return false; } }; class Solution { public: vector<vector<int> > permuteUnique(vector<int> &num) { vector<vector<int> > res; if(num.size() == 0)return res; vector<int> tmpres; permuteRecur(num, 0, res, tmpres); return res; } void permuteRecur(vector<int> &num, int index, vector<vector<int> >&res, vector<int>&tmpres) { if(index == num.size()) { res.push_back(tmpres); return; } unordered_set<int> umap; for(int i = index; i < num.size(); i++) if(umap.find(num[i]) == umap.end()) { umap.insert(num[i]); swap(num[index], num[i]); tmpres.push_back(num[index]); permuteRecur(num, index+1, res, tmpres); tmpres.pop_back(); swap(num[index], num[i]); } } }; 算法3： 我們知道c++STL中有個函數next_permutation,這個函數時求某個排列的下一個大的排列。所謂的下一個大的排列可以如下解釋：如果把數組元素看成是某個字符，這些字符組成一個字符串，下一個大的排列就是比當前排列代表的字符串更大（按字典序比較），且不存在介於兩個字符串之間的字符串。例如對於字符串abc，它的下一個大排列是acb。 對於某個排列，我們如下求它的下一個大的排列： 從最尾端開始往前尋找兩個相鄰的元素，兩者滿足i < ii（令第一個元素為i，第二個元素為ii） 如果沒有找到這樣的一對元素則，表明當前的排列是最大的，沒有下一個大的排列 如果找到，再從末尾開始找出第一個大於i的元素，記為j 交換元素i, j，再將ii後面的所有元素顛倒排列 按照的STL實現，如果某個排列沒有比他大的下一個排列，調用這個函數還是會把原排列翻轉，即得到最小的排列 有了這個函數後，這一題，我們先對數組按照升序排序，這樣初始排列就是最小的，然後循環對數組求next_permutation，直到找不到下一個大的排列。 class Solution { public: vector<vector<int> > permuteUnique(vector<int> &num) { vector<vector<int> > res; if(num.size() == 0)return res; sort(num.begin(), num.end()); res.push_back(num); while(mynext_permutation(num))res.push_back(num); return res; } bool mynext_permutation(vector<int>&num) { int n = num.size(); if(n <= 1)return false; for(int i = n-2, ii = n-1; i >= 0; i--,ii--) { if(num[i] < num[ii]) { int j = n-1; while(num[j] <= num[i])j--;//從尾部找到第一個比num[i]大的數，一定可以找到 swap(num[i], num[j]); reverse(num.begin()+ii, num.end()); return true; } } reverse(num.begin(), num.end()); return false; } }; STL還有一個prev_permutation函數，求某個排列的上一個比他小的排列，方法和next_permutation相似： 對於某個排列，我們如下求它的上一個更小的排列： 從最尾端開始往前尋找兩個相鄰的元素，兩者滿足i > ii（令第一個元素為i，第二個元素為ii） 如果沒有找到這樣的一對元素則，表明當前的排列是最小的，沒有下一個更小的排列 如果找到，再從末尾開始找出第一個小於i的元素，記為j 交換元素i, j，再將ii後面的所有元素顛倒排列 按照的STL實現，如果某個排列沒有比他小的下一個排列，調用這個函數還是會把原排列翻轉，即得到最大的排列 有了這個函數後，這一題，我們先對數組按照降序排序，這樣初始排列就是最大的，然後循環對數組求prev_permutation，直到找不到下一個更小的排列。 class Solution { public: vector<vector<int> > permuteUnique(vector<int> &num) { vector<vector<int> > res; if(num.size() == 0)return res; sort(num.begin(), num.end(), greater<int>()); res.push_back(num); while(myprev_permutation(num))res.push_back(num); return res; } bool myprev_permutation(vector<int>&num) { int n = num.size(); if(n <= 1)return false; for(int i = n-2, ii = n-1; i >= 0; i--,ii--) { if(num[i] > num[ii]) { int j = n-1; while(num[j] >= num[i])j--;//從尾部找到第一個比num[i]小的數，一定可以找到 swap(num[i], num[j]); reverse(num.begin()+ii, num.end()); return true; } } reverse(num.begin(), num.end()); return false; } };
