非负整数可重集O(n)去重并排序
可重集是指元素可重复的集合，对于在一定区间内的正整数集，比如[1,n]，我们可以在不不使用任何额外空间(包括不使用O（1）的空间)的情况下，用O（n）的时间复杂度完成集合的去重并排序，这种O(n)的算法，是理想的联机算法。
思路：本质上和桶排序类似，用数组下标来表示存在的元素，数组中的元素作为flag。
对于正整数可重集来说，打标记的方法可以是将元素变负（思考，为什么不是随便赋一个规定的值），负整数依次类推。
对于元素属于[1,n]的集合（n为元素个数），我们可以用下面的代码完成上述操作并取出元素，总时间是O(2n)
void removeDuplicates(int *a,int len){
for(int i=;i<len;i++)
a[abs(a[i])-] = -abs(a[abs(a[i])-]);//如果元素a[i]存在，则将a[abs(a[i])-1] 变负,下标0 ~ n-1 对应1 ~ n
for(int i=;i<len;i++)if(a[i]<)//如果a[i]<0 ，则说明i+1存在 ，取出
printf("%d ",i+);
}
int main(){
int seq[] = {,,,,,,,,};
removeDuplicates(seq,sizeof(seq)/sizeof(int));
return ;
}
获得可重集全排列：
自己玩：
可重集是指元素可重复的集合，可重集的全排列通常可以递归地进行求解。
对于n个元素不重复的集合来说，我们可以递归为：
- 将第k个元素（k=1，2...n）放到集合首部
- 求解剩下n-k个元素的集合的全排列
- 重复1和2，直到集合的元素为空时，打印整个集合
实现的代码（此处是以字符串为例），其中len表示字符串s的长度。注意，这里s必须定义为数组，如果定义为指针，将会引发错误，具体请看我的另一篇博客：C++指针和数组的区别中的情况2
void swap(char &i,char &j){
char t=i;i=j;j=t;
}
void permutation(char s[],int left,int len){
if(left==len)printf("%s\n",s);
else{
for(int k=left;k<len;k++){
if(s[left]!=s[k])swap(s[left],s[k]);
//递归求解n-k个元素的全排列
permutation(s,left+,len);
if(s[left]!=s[k])swap(s[left],s[k]);
}
}
}
需要注意：这种实现不是遵从字典序的实现
当我们需要打印可重集的全排列时，我们只需对递归调用的部分稍作改动
- 重复的情况要保证出现，所以，当left==k的时候，代表第一次递归，此时，应当保留
- 除了1之外，如果s[left]和s[k]仍有相等情况，则不应交换和递归，因为此时若递归，会造成重复
简单修改上述代码，实现如下：
void swap(char &i,char &j){
char t=i;i=j;j=t;
}
void permutation(char s[],int left,int len){
if(left==len)printf("%s\n",s);
else{
for(int k=left;k<len;k++){
//增加了上文的两个判定条件
if(k==left||s[left]!=s[k]){
swap(s[left],s[k]);
permutation(s,left+,len);
swap(s[left],s[k]);
}
}
}
}
同样，这种实现不是遵从字典序的实现。
当然，我们很多时候都需要按照字典序进行排列，说实话，我觉得我是很讨厌手写这个的，毕竟相当的麻烦，所以，就有了下面这个：
黑科技：STL中的next_permutation(s,s+n)
#include<algorithm>
using namespace std;
void permutation(char s[],int len){
sort(s,s+len);//一定要先排序
do{
puts(s);
}while(next_permutation(s,s+len));
}
这是货真价实的字典序的全排列，今天就到这，拜拜~