题目

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], [2,1,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** permuteUnique(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);
    //依次复制上个全排列，然后使用之前的算法，对其递增，找到下一个全排列
    int i=1;
    while(i<(*returnSize))
    {
        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;
        }
        //当达到最大字典序的全排列时候，退出，并保存数组个数
        if(i1<0)
        {
            *returnSize=i;
            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);
        i++;
    }
    return ans;
}