题目
Given a collection of distinct 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], [3,2,1]]
分析
寻找一系列数字的全排列，以数组形式输出
1，是先找一个最小字典序的全排列，然后依次增大。
void sort(int *a, int left, int right)
{
if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
{
return ;
}
int i = left;
int j = right;
int key = a[left];
while(i < j) /*控制在当组内寻找一遍*/
{
while(i < j && key <= a[j])
/*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
{
j--;/*向前寻找*/
}
a[i] = a[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
a[left]，那么就是给key）*/
while(i < j && key >= a[i])
/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
{
i++;
}
a[j] = a[i];
}
a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}
/**
* Return an array of arrays of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int** permute(int* nums, int numsSize, int* returnSize) {
*returnSize=1;
for(int i=1;i<=numsSize;i++)
{
*returnSize=(*returnSize)*i;
}
//先初始化所有的二维数组
int **ans=(int **)malloc(sizeof(int *)*(*returnSize));
ans[0]=(int *)malloc(sizeof(int)*numsSize);
for(int j=0;j<numsSize;j++)
{
ans[0][j]=nums[j];
}
//排序，得到最小字典序的全排列
sort(ans[0],0,numsSize-1);
//依次复制上个全排列，然后使用之前的算法，对其递增，找到下一个全排列
for(int i=1;i<(*returnSize);i++)
{
ans[i]=(int *)malloc(sizeof(int)*numsSize);
for(int j=0;j<numsSize;j++)
{
ans[i][j]=ans[i-1][j];
}
int i1=numsSize-2,j1=numsSize-1,temp=0,p;
while(i1>=0)
{
if(ans[i][i1]>=ans[i][j1])
{
i1--;
j1--;
}
else
break;
}
p=j1;
j1++;
while(j1<numsSize)
{
if(ans[i][j1]>ans[i][i1]&&ans[i][j1]<ans[i][p])
p=j1;
j1++;
}
if(i1>=0)
{
temp=ans[i][i1];
ans[i][i1]=ans[i][p];
ans[i][p]=temp;
sort(ans[i],i1+1,numsSize-1);
}
else
sort(ans[i],0,numsSize-1);
}
return ans;
}
2，当然也可以使用递归进行二维数组的赋值,就是对某一列依次赋值，个数为剩下的数字的全排列总数，之后对下一列进行剩下数字的全排列
void Permutation(int **ans,int k,int p,int *nums,int numsSize)//k第几列 p某个相同的数字第几行开始的
{
//剩下一个数字，就直接赋值返回
if(numsSize==1)
{
ans[p][k]=nums[0];
return;
}
//找到一个数字应该重复多少次
int temp=1;
for(int i=1;i<numsSize;i++)
{
temp=temp*i;
}
//
for(int i=0;i<numsSize;i++)
{
for(int j=p;j<p+temp;j++)
{
ans[j][k]=nums[i];
}
//对剩下的数字再单独得到一个数组，以便递归调用
int *numsTemp=(int *)malloc(sizeof(int)*(numsSize));
for(int j=0;j<i;j++)
{
numsTemp[j]=nums[j];
}
for(int j=i;j<numsSize-1;j++)
{
numsTemp[j]=nums[j+1];
}
//for(int j=0;j<numsSize-1;j++)
//{
// printf("%d ",numsTemp[j]);
//}
//printf("\n");
Permutation(ans,k+1,p,numsTemp,numsSize-1);
free(numsTemp);
p=p+temp;
}
}
/**
* Return an array of arrays of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int** permute(int* nums, int numsSize, int* returnSize) {
*returnSize=1;
for(int i=1;i<=numsSize;i++)
{
*returnSize=(*returnSize)*i;
}
int **ans=(int **)malloc(sizeof(int *)*(*returnSize));
for(int i=0;i<(*returnSize);i++)
{
ans[i]=(int *)malloc(sizeof(int)*numsSize);
}
Permutation(ans,0,0,nums,numsSize);
return ans;
}
