題目
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]]
分析
尋找一系列數(shù)字的全排列蒸其，以數(shù)組形式輸出
1取胎，是先找一個(gè)最小字典序的全排列哥纫，然后依次增大颖对。
void sort(int *a, int left, int right)
{
if(left >= right)/*如果左邊索引大于或者等于右邊的索引就代表已經(jīng)整理完成一個(gè)組了*/
{
return ;
}
int i = left;
int j = right;
int key = a[left];
while(i < j) /*控制在當(dāng)組內(nèi)尋找一遍*/
{
while(i < j && key <= a[j])
/*而尋找結(jié)束的條件就是百揭，1，找到一個(gè)小于或者大于key的數(shù)（大于或小于取決于你想升
序還是降序）2抡笼，沒(méi)有符合條件1的，并且i與j的大小沒(méi)有反轉(zhuǎn)*/
{
j--;/*向前尋找*/
}
a[i] = a[j];
/*找到一個(gè)這樣的數(shù)后就把它賦給前面的被拿走的i的值（如果第一次循環(huán)且key是
a[left]仔戈，那么就是給key）*/
while(i < j && key >= a[i])
/*這是i在當(dāng)組內(nèi)向前尋找，同上拧廊，不過(guò)注意與key的大小關(guān)系停止循環(huán)和上面相反杂穷，
因?yàn)榕判蛩枷胧前褦?shù)往兩邊扔，所以左右兩邊的數(shù)大小與key的關(guān)系相反*/
{
i++;
}
a[j] = a[i];
}
a[i] = key;/*當(dāng)在當(dāng)組內(nèi)找完一遍以后就把中間數(shù)key回歸*/
sort(a, left, i - 1);/*最后用同樣的方式對(duì)分出來(lái)的左邊的小組進(jìn)行同上的做法*/
sort(a, i + 1, right);/*用同樣的方式對(duì)分出來(lái)的右邊的小組進(jìn)行同上的做法*/
/*當(dāng)然最后可能會(huì)出現(xiàn)很多分左右卦绣，直到每一組的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;
}
//先初始化所有的二維數(shù)組
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);
//依次復(fù)制上個(gè)全排列，然后使用之前的算法滤港，對(duì)其遞增廊蜒，找到下一個(gè)全排列
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趴拧，當(dāng)然也可以使用遞歸進(jìn)行二維數(shù)組的賦值,就是對(duì)某一列依次賦值，個(gè)數(shù)為剩下的數(shù)字的全排列總數(shù)山叮，之后對(duì)下一列進(jìn)行剩下數(shù)字的全排列
void Permutation(int **ans,int k,int p,int *nums,int numsSize)//k第幾列 p某個(gè)相同的數(shù)字第幾行開(kāi)始的
{
//剩下一個(gè)數(shù)字著榴，就直接賦值返回
if(numsSize==1)
{
ans[p][k]=nums[0];
return;
}
//找到一個(gè)數(shù)字應(yīng)該重復(fù)多少次
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];
}
//對(duì)剩下的數(shù)字再單獨(dú)得到一個(gè)數(shù)組，以便遞歸調(diào)用
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;
}
