题目

英文

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

中文

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

思路

思路1

  • 借鉴之前做的第k个排序
  • 把所有的排序塞进一个二维数组里

思路2

思路一打败了百分之56的人，我觉得还有其他建单的思路。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int jiecheng(int n)
{
    int ret = 1;
    while(n > 0)
    {
        ret = ret *n;
        n--;
    }
    return ret;
}
int** permute(int* nums, int numsSize, int* returnSize) {
    *returnSize = jiecheng(numsSize);
    //返回的二维数组
    int** ret = (int**)malloc((sizeof(int*)*(*returnSize)));
    //记录头指针
    int** current = ret;
    //标识进位
    int* tmp = (int*)malloc(sizeof(int)*numsSize);
    tmp[numsSize-1] = 1;
    for(int i = numsSize-2; i>=0; i--)
    {
        tmp[i] = tmp[i+1]*(numsSize-1-i);
    }
    //标识是否使用
    int *flag = (int*)malloc(sizeof(int)*numsSize);
    //初始化所有都为0；
    int idx = 0, t = 0, k =0, m = 0;
    memset(flag, 0, sizeof(int)*numsSize);
    //输出每一个组合
    for(int i = 1; i <= (*returnSize); i++)
    {
        int* tmp1 = (int*)malloc(sizeof(int)*numsSize); 
        //初始化
        idx = 0, t = 0; k = i , m=0;
        memset(flag, 0, sizeof(int)*numsSize);
        for(int j = 0; j < numsSize; j++)
        {
            //取当前应取数字所在位
            t = (k-1)/tmp[j];
            //保留数坐在位置
            idx =t;
            for( m  = 0; m < numsSize;m++)
            {
                //寻找最左未使用的数
                if(!flag[m])
                {
                    t--;
                    if(t == -1)
                    {
                        break;
                    }
                }
            }
            tmp1[j] = nums[m];
            // printf("m:%d,",m);
            // printf("j:%d,",j);
            // printf("%d,",tmp1[j]);
            flag[m] = 1;
            k -= (idx*tmp[j]);
        }
        (*current) = tmp1;
        current++;
    }
    return ret;
}