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