H****r
发帖数: 2801 | 1 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].
注意{ -1,2,0,-1,1,0,1 }有630个不同的permutations
本人把结果存到个set里面去才避免了重复，求正解 | w****x
发帖数: 2483 | 2 前天刚做过
//permutation of string with duplicate characters
//different from the subset problem, can't solve duplicated chars
//situation by sorting the array
void _inner_print(char strOrg[], char strCur[], int nLen)
{
assert(strOrg && strCur && nLen >= 0);
if (0 == nLen)
{
cout<
return;
}
//record if a character is calculated as a header
//to eliminate duplicated characters
bool bRec[256];
memset(bRec, 0, sizeof(bRec));
for (int i = 0; i < nLen; i++)
{
if (!bRec[strCur[i]])
{
swap(strCur[0], strCur[i]);
_inner_print(strOrg, strCur+1, nLen-1);
swap(strCur[0], strCur[i]);
bRec[strCur[i]] = true;
}
}
} | L***Q
发帖数: 508 | 3 大牛常驻本版传业授道解惑啊
【在 w****x 的大作中提到】
: 前天刚做过
: //permutation of string with duplicate characters
: //different from the subset problem, can't solve duplicated chars
: //situation by sorting the array
: void _inner_print(char strOrg[], char strCur[], int nLen)
: {
: assert(strOrg && strCur && nLen >= 0);
: if (0 == nLen)
: {
: cout<
| w****x
发帖数: 2483 | 4 刚发现题目不大一样, 我的是string的permutation.
一般去重都是先排序, 不过permutation这题好像排序搞不定, 不知道最好的解法是什
么 | l*****a
发帖数: 14598 | 5 if no extra memory,how can u solve this?
【在 w****x 的大作中提到】
: 前天刚做过
: //permutation of string with duplicate characters
: //different from the subset problem, can't solve duplicated chars
: //situation by sorting the array
: void _inner_print(char strOrg[], char strCur[], int nLen)
: {
: assert(strOrg && strCur && nLen >= 0);
: if (0 == nLen)
: {
: cout<
| w****x
发帖数: 2483 | 6
那还真不会, 总得找个办法记录这一轮哪些数已经整过了啊
【在 l*****a 的大作中提到】
: if no extra memory,how can u solve this?
| H****r
发帖数: 2801 | 7 这个你试过吗？偶怎么结果是空的？
【在 w****x 的大作中提到】
: 前天刚做过
: //permutation of string with duplicate characters
: //different from the subset problem, can't solve duplicated chars
: //situation by sorting the array
: void _inner_print(char strOrg[], char strCur[], int nLen)
: {
: assert(strOrg && strCur && nLen >= 0);
: if (0 == nLen)
: {
: cout<
| l*****a
发帖数: 14598 | 8 看起来不牛
1) sort
2) when do loop to create permutaiton
for(int i=start;i
{
if(a[i]==a[i-1])&&(i!=start) continue;
...
}
【在 w****x 的大作中提到】
:
: 那还真不会, 总得找个办法记录这一轮哪些数已经整过了啊
| H****r
发帖数: 2801 | 9 这个估计size一般不会超过256，string如果可以解也行啊，大牛能说说解法怎么避免
重复的吗？
【在 w****x 的大作中提到】
: 刚发现题目不大一样, 我的是string的permutation.
: 一般去重都是先排序, 不过permutation这题好像排序搞不定, 不知道最好的解法是什
: 么
| w****x
发帖数: 2483 | 10
给各完整的行不
【在 l*****a 的大作中提到】
: 看起来不牛
: 1) sort
: 2) when do loop to create permutaiton
: for(int i=start;i: {
: if(a[i]==a[i-1])&&(i!=start) continue;
: ...
: }
| | | H****r
发帖数: 2801 | 11 这个和偶的想法差不多，但是这样还不能完全消除重复... 上面那个例子偶解出696个
，冗余了66个。 哭死...
【在 l*****a 的大作中提到】
: 看起来不牛
: 1) sort
: 2) when do loop to create permutaiton
: for(int i=start;i: {
: if(a[i]==a[i-1])&&(i!=start) continue;
: ...
: }
| l*****a
发帖数: 14598 | 12 qsort(a,0,size-1);
void GetPermutation(int a[],int size,int start)
{
if(start==size) {...;return;}
for(int i=start;i
{
if((i!=start)&&(a[i]==a[i-1]) continue;
swap(a,start,i);
GetPermutation(a,size,start+1);
swap(a,i,start);
}
}
【在 w****x 的大作中提到】
:
: 给各完整的行不
| w****x
发帖数: 2483 | 13
这样可以吗, 你swap以后就破坏了排序性, 后面的递归就不能把数组看成排好序的了
【在 l*****a 的大作中提到】
: qsort(a,0,size-1);
: void GetPermutation(int a[],int size,int start)
: {
: if(start==size) {...;return;}
: for(int i=start;i: {
: if((i!=start)&&(a[i]==a[i-1]) continue;
: swap(a,start,i);
: GetPermutation(a,size,start+1);
: swap(a,i,start);
| l*****a
发帖数: 14598 | 14 u r right,
wait...
【在 w****x 的大作中提到】
:
: 这样可以吗, 你swap以后就破坏了排序性, 后面的递归就不能把数组看成排好序的了
| b******u
发帖数: 81 | 15 public static List> GetPermutation ( List numbers )
{
List> result = new List> ();
if ( numbers.Count () == 1 ) result.Add ( new List { numbers [ 0 ]
} );
if ( numbers.Count () > 1 )
{
List distinctNumbers = numbers.Distinct ().ToList ();
foreach ( int n in distinctNumbers )
{
List otherNumbers = numbers.ToList ();
otherNumbers.Remove ( n );
List> perm = GetPermutation ( otherNumbers );
foreach ( List list in perm )
{
list.Add ( n );
result.Add ( list );
}
}
}
return result;
} | H****r
发帖数: 2801 | 16 这个跟偶写的好像啊，终于搞出个没有冗余的，但不保证最优，就是把那俩swap改成
array shift, 这样顺序不会变... 小happy下...
当然array shift这个操作也不常用，要有更好的做法就好了...
【在 l*****a 的大作中提到】
: qsort(a,0,size-1);
: void GetPermutation(int a[],int size,int start)
: {
: if(start==size) {...;return;}
: for(int i=start;i: {
: if((i!=start)&&(a[i]==a[i-1]) continue;
: swap(a,start,i);
: GetPermutation(a,size,start+1);
: swap(a,i,start);
| p*****2
发帖数: 21240 | 17 lolhaha做这种题特别的牛逼。这点我特别服他。 | l*****a
发帖数: 14598 | 18 这题做的不对，丢人了
另外面试从来没碰上过排列组合题。。
【在 p*****2 的大作中提到】
: lolhaha做这种题特别的牛逼。这点我特别服他。
| p*****2
发帖数: 21240 | 19
不对呀？那我得好好看一下题。刚才开会去了。
【在 l*****a 的大作中提到】
: 这题做的不对，丢人了
: 另外面试从来没碰上过排列组合题。。
| p*****2
发帖数: 21240 | | | | f*****i
发帖数: 835 | 21 写了一个，
用hash_map记录unique的值和使用情况
请大牛帮看看
void getPerM(vector& a, vector >& result){
hash_map b;
for(int i=0; i
if(b.find(a[i])==b.end()) b[a[i]] = 1;
else b[a[i]]++;
}
vector t;
getPerM(b, t, result, a.size());
}
void getPerM(hash_map& m, vector t, vector >&
result,int size){
hash_map::iterator it=m.begin();
for(;it!=m.end();it++){
if(it->second > 0){
t.push_back(it->first);
it->second--;
if(t.size()==size) result.push_back(t);
else getPerM(m,t,result,size);
it->second++;
t.pop_back();
}
} | i**********e
发帖数: 1145 | 22 有两种解法，第一种就像 lolhaha 的思路：
先排序，这样能跳过同样的元素，避免重复。
第二种是实现 next_permutation()，
next_permutation 的好处是没有递归，而且可以处理重复。
算法可以参考这里，解说的很好：
http://wordaligned.org/articles/next-permutation#tocwhats-happe
代码也可以参考 C++ STL 里的 next_permutation.
【在 l*****a 的大作中提到】
: 看起来不牛
: 1) sort
: 2) when do loop to create permutaiton
: for(int i=start;i: {
: if(a[i]==a[i-1])&&(i!=start) continue;
: ...
: }
| w****x
发帖数: 2483 | 23
我会用hash map在每一层递归记录swap到a[0]的数据来避免重复,
但是排序的话swap以后就不能保证下层递归的排序性啊,
next_permutation的确是种解法, 赞一个, 就是难了点
【在 i**********e 的大作中提到】
: 有两种解法，第一种就像 lolhaha 的思路：
: 先排序，这样能跳过同样的元素，避免重复。
: 第二种是实现 next_permutation()，
: next_permutation 的好处是没有递归，而且可以处理重复。
: 算法可以参考这里，解说的很好：
: http://wordaligned.org/articles/next-permutation#tocwhats-happe
: 代码也可以参考 C++ STL 里的 next_permutation.
| i**********e
发帖数: 1145 | 24 没想明白为什么要用hash_map呢，可以省些空间吗？
用一个table来记录用过的index，然后跳过重复的元素代码如下：
vector > permuteUnique(vector &num) {
sort(num.begin(), num.end());
vector > ret;
int n = num.size();
bool *used = new bool[n];
int *index = new int[n];
memset(used, 0, n*sizeof(bool));
permuteUnique(num, used, index, 0, ret);
delete[] used;
delete[] index;
return ret;
}
void permuteUnique(vector &num, bool used[], int index[],
int pos, vector > &ret) {
int n = num.size();
if (pos == n) {
vector ans;
for (int i = 0; i < n; i++) {
ans.push_back(num[index[i]]);
}
ret.push_back(ans);
return;
}
for (int i = 0; i < n; ) {
if (used[i]) { i++; continue; }
used[i] = true;
index[pos] = i;
permuteUnique(num, used, index, pos+1, ret);
used[i] = false;
int j = i;
while (i < n && num[i] == num[j]) i++;
}
}
【在 w****x 的大作中提到】
:
: 我会用hash map在每一层递归记录swap到a[0]的数据来避免重复,
: 但是排序的话swap以后就不能保证下层递归的排序性啊,
: next_permutation的确是种解法, 赞一个, 就是难了点
| f*****i
发帖数: 835 | 25 我觉着用hash_map就是省掉了排序和这个
while (i < n && num[i] == num[j]) i++;
不过速度上hash_map不一定快
【在 i**********e 的大作中提到】
: 没想明白为什么要用hash_map呢，可以省些空间吗？
: 用一个table来记录用过的index，然后跳过重复的元素代码如下：
: vector > permuteUnique(vector &num) {
: sort(num.begin(), num.end());
: vector > ret;
: int n = num.size();
: bool *used = new bool[n];
: int *index = new int[n];
: memset(used, 0, n*sizeof(bool));
: permuteUnique(num, used, index, 0, ret);
| s****r
发帖数: 125 | 26 The solution: The Art of Computer Programming, Volume 4 Fascicle 2:
Generating All Tuples and Permutations by D. E. Knuth | w****x
发帖数: 2483 | 27
恩, 对, 记录index更好, 谢了.
【在 i**********e 的大作中提到】
: 没想明白为什么要用hash_map呢，可以省些空间吗？
: 用一个table来记录用过的index，然后跳过重复的元素代码如下：
: vector > permuteUnique(vector &num) {
: sort(num.begin(), num.end());
: vector > ret;
: int n = num.size();
: bool *used = new bool[n];
: int *index = new int[n];
: memset(used, 0, n*sizeof(bool));
: permuteUnique(num, used, index, 0, ret);
| H****r
发帖数: 2801 | 28 赞大牛！
这题要是可以用std library 直接调用next_permutation估计可以在几分钟时间搞定
lol
这个next_permutation的文章很不错啊@@
递归的感觉也不错啊，偶写了个没有记录swap过的id的，不过得用list插入，程序缺乏
美感就不贴了...
【在 i**********e 的大作中提到】
: 有两种解法，第一种就像 lolhaha 的思路：
: 先排序，这样能跳过同样的元素，避免重复。
: 第二种是实现 next_permutation()，
: next_permutation 的好处是没有递归，而且可以处理重复。
: 算法可以参考这里，解说的很好：
: http://wordaligned.org/articles/next-permutation#tocwhats-happe
: 代码也可以参考 C++ STL 里的 next_permutation.
| p*****2
发帖数: 21240 | 29
谁能写个java的版本看看？
【在 i**********e 的大作中提到】
: 没想明白为什么要用hash_map呢，可以省些空间吗？
: 用一个table来记录用过的index，然后跳过重复的元素代码如下：
: vector > permuteUnique(vector &num) {
: sort(num.begin(), num.end());
: vector > ret;
: int n = num.size();
: bool *used = new bool[n];
: int *index = new int[n];
: memset(used, 0, n*sizeof(bool));
: permuteUnique(num, used, index, 0, ret);
| H****r
发帖数: 2801 | 30 感谢大家特别是leetcode大牛的回复，
后来还是在大家的启发下重新写了， 主要改动就是记录unique keys这样如果初始数组
有元素重复多次时可以省点计算（比如数组只有0和1）：
struct ItmCount {
int x;
int count;
};
vector > UniquePermutations(vector &nums) {
vector > results;
vector items = CountUniqueItems(nums);
GeneratePermutation(results, nums, 0, items);
return results;
}
void GeneratePermutation(vector >& results,
vector& numbers, int idx, vector& items) {
if (idx == numbers.size()) {
results.push_back(numbers);
return;
}
for (int i=0; i
if (items[i].count > 0) {
numbers[idx] = items[i].x;
--items[i].count;
GeneratePermutation(results, numbers, idx+1, items);
++items[i].count;
}
}
}
///
vector CountUniqueItems(vector &nums) {
...
【在 i**********e 的大作中提到】
: 没想明白为什么要用hash_map呢，可以省些空间吗？
: 用一个table来记录用过的index，然后跳过重复的元素代码如下：
: vector > permuteUnique(vector &num) {
: sort(num.begin(), num.end());
: vector > ret;
: int n = num.size();
: bool *used = new bool[n];
: int *index = new int[n];
: memset(used, 0, n*sizeof(bool));
: permuteUnique(num, used, index, 0, ret);
| | | p*****2
发帖数: 21240 | 31 看了leetcode的题解。谁帮我回忆一下。那个sort+swap的解是解决的什么问题来着？
我一开始以为解决的就是这个问题。 | p*****2
发帖数: 21240 | 32 这题面试的时候写起来也不容易。明天得赶紧练练。 |
|
