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]
.
A:
**********************第五遍*********************
不用排序,就是每次增加一个数的时候, 直接在后面插入,一直插入到发现这个数为止。
Learned:class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> res; res.push_back(vector<int>{nums[0]}); for(int i = 1; i<nums.size(); i++){ int val = nums[i]; vector<vector<int>> newRes; for(auto line : res){ // append at tail untill we see for(int j = line.size();j>=0;j--){ if(j == line.size() || line[j] != val){ vector<int> newLine(line); newLine.insert(newLine.begin()+j,val); newRes.push_back(newLine); }else{ break; } } } res = newRes; } return res; } };
vector<int> a = b; // where b is declared as vector<int> b{2,3,5,6}; 这样的是deep copy. 所以上面的代码还可以减少copy
*********************第一遍*****************
原本的思路是,先treat them as all distinct, 再删去重复的。
但是,这样,估计会太复杂,冗余太多。
后来想,每一重循环: 先extract unique items,找到其所有permutations,
再加入。 ---可是,这样, 还是需要处理重复的情况。
经过分析, 当我们要加入m个value的值。 我们发现,有一样是i不变的,就是要加入的位置。(前面加入后,这个值也可以很容易地 update)。 因此,我们每次固定一个要加入的位置,确定要加入的value的个数。然后recursively 计算剩下的value 的position 的permutation。
这样的思路,最大的好处是,加入的时候,不用考虑已加入的permutation是否有重复的。
代码如下:
public class Solution { public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { // use DP rather than recursively calling to find them ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>(); if (num.length == 0) { return all; } // add the first one Arrays.sort(num); int i =0; while(i<num.length) { int newNumber = num[i]; // count how many newNumber exist in the input int nNum = 1; while (i + 1 < num.length && num[i + 1] == newNumber) { nNum++; i++; } all = addNewNumbers2Al(all, nNum, newNumber); i ++;; } return all; } private ArrayList<ArrayList<Integer>> addNewNumbers2Al( ArrayList<ArrayList<Integer>> all, int nNum, int newNumber) { // if all is still empty if (all.size() == 0) { ArrayList<Integer> al = new ArrayList<Integer>(); for (int i = 0; i < nNum; i++) { al.add(newNumber); } all.add(al); return all; } int permuLength = all.get(0).size();// the length of the existing // permutations // also use ArrayList to save the positions, and its how many newNumber // is stored at that position ArrayList<ArrayList<Integer>> returnedAll = new ArrayList<ArrayList<Integer>>(); ArrayList<ArrayList<Integer>> allPos = buildPermu(0, permuLength, nNum); // at position i, add allPos[i] number of newNumbers for(int i =0;i<allPos.size();i++){ ArrayList<Integer> alPos = allPos.get(i); // for this inserting positions permutation ArrayList<ArrayList<Integer>> newAll = copyAndInsertList(all,alPos,newNumber); returnedAll.addAll(newAll); } return returnedAll; } ArrayList<ArrayList<Integer>> buildPermu(int startPos, int endPos, int nNum) { // input : startPosisin and end Position of the inerted value, // GOAL: for positions of length nPos, we can add nNum of a specific // values, // we need return how many values we need ArrayList<ArrayList<Integer>> allPos = new ArrayList<ArrayList<Integer>>(); if (nNum == 0) { ArrayList<Integer> al = new ArrayList<Integer>(); for (int i = startPos; i <= endPos; i++) al.add(0); // all add 0 at tail allPos.add(al); return allPos; } if (startPos == endPos) { ArrayList<Integer> al = new ArrayList<Integer>(); al.add(nNum); allPos.add(al); return allPos; } // now number of positions > 1 and number of for (int k = 0; k <= nNum; k++) { // k is the number of values that // inserted at beginning // first return all list before ArrayList<ArrayList<Integer>> allAddKatStart = buildPermu(startPos+1, endPos, nNum - k); // insert at the begining of the list for (int t = 0; t < allAddKatStart.size(); t++) { allAddKatStart.get(t).add(0, k);// insert at beginning } // NOW,allAddKatStart contains all the permuations with the first permuation is k at startPosition allPos.addAll(allAddKatStart); } return allPos; } private ArrayList<ArrayList<Integer>> copyAndInsertList( ArrayList<ArrayList<Integer>> all, ArrayList<Integer> alPos,int targetValue) { // create a new copy of all, and then add newNumber at position k ArrayList<ArrayList<Integer>> newAll = new ArrayList<ArrayList<Integer>>(); for (int i = 0; i < all.size(); i++) { // for each list, copy and // insert newNumber ArrayList<Integer> alOld = all.get(i); ArrayList<Integer> alNew = new ArrayList<Integer>(); for (int j = 0; j < alOld.size(); j++) { alNew.add(alOld.get(j)); } newAll.add(alNew); } // now we have the copied all, named as newAll for(int i =0;i<newAll.size();i++){ ArrayList<Integer> tmpAl = newAll.get(i ); // for each old permutation // now we have the new list, we need insert the targetValue at positions specified by alPos for(int insertPos =alPos.size()-1;insertPos>=0;insertPos-- ){ // we are working on position j // add alPos[j] time of targetValue for(int k = 0;k<alPos.get(insertPos);k++) tmpAl.add(insertPos , targetValue); } } return newAll; } }
Mistakes:
哎,太多了。一开始是思路不对。
后来,后来,从周四下午,在家里电脑上想了想,找到路子了。黑色星期五的下午,才突然想起来,可以把position也做permutation。
然后,晚上,来了,干了快2个小时,才弄完。
语法错误啊什么的,倒是不多。 没怎么用debug。 思路啊,思路。
-------------------第二遍 --------------很简单嘛,用 recursively calling ---------------------------
思想是: 对每一个不同的值,插入到 (删去它之后的permute的list)的第一个位置。
class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { return helper(nums,0); } private: vector<vector<int>> helper(vector<int> & nums, int start){ int n = nums.size(); vector<vector<int>> res; if(start >=n) return res; if(start == n-1){ res.push_back(vector<int>{nums[start]}); }else{ for(auto & line : helper(nums,start+1)){ for(int i =line.size(); i>=0;i--){ auto newLine = line; newLine.push_back(nums[start]); if(i != line.size() && newLine[i] == newLine.back() ){ break; }else{ newLine[line.size()] = newLine[i];//swap potion i and the last newLine[i] = nums[start]; res.push_back(newLine); } } } } return res; } };
------------------------- 3 rd pass-----------------------------
每次删掉最前面所有的相同的值,假设是k 个value ==3的值。 那么我们把剩下的permute好之后,再把这k个3 插入到结果里去。
public class Solution { public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { Arrays.sort(num); return permute(num, 0); } private ArrayList<ArrayList<Integer>> permute(int[] num,int start){ // find how many values at start ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>(); if(start >= num.length) return all; int count = 0; int val = num[start]; while( start<num.length && num[start] == val ){ start++; count++; } // get result without this value (and count) ArrayList<ArrayList<Integer>> oneLess = permute(num, start); // input # of val into the oneLess list all.addAll(insert2permute( oneLess, val,count ,0)); return all; } private ArrayList<ArrayList<Integer>> insert2permute( ArrayList<ArrayList<Integer>> all, int val, int count,int startIndex ){ // insert the total amount (count) of values (val ) into the arrayList (all) if(count<=0){ return all; } if(all.size() ==0){ ArrayList<Integer> al = new ArrayList<Integer>(); for(int i =0;i<count;i++) al.add(val); all.add(al); return all; } // now all is not empty, and count >= 1 // begining insert position ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); for(int i=startIndex;i<=all.get(0).size();i++){ // add val at each startIndex position ArrayList<ArrayList<Integer>> newAll = copyList(all); for(ArrayList<Integer> al : newAll){ al.add(i,val); } result.addAll(insert2permute( newAll, val, count-1, i+1)); } return result; } private ArrayList<ArrayList<Integer>> copyList(ArrayList<ArrayList<Integer>> all){ ArrayList<ArrayList<Integer>> newAll = new ArrayList<ArrayList<Integer>>(); if(all.size()==0) return newAll; for(ArrayList<Integer> al:all){ ArrayList<Integer> newAl = new ArrayList<Integer>(); for(int val : al){ newAl.add(val); } newAll.add(newAl); } return newAll; } }
Learned:
No comments:
Post a Comment