每周一道算法题(三十五)

最近换了工作，房子到期了又到处去看房子，加上周末还要上课做作业，感觉好累，精神总不容易集中，导致本周的题目断断续续弄了好几天才做出来，看来还是要好好休息啊。本周题目难度级别'Medium'，使用语言C

题目：本周题目很简单，就是给你一组不重复的数，要求返回这组数的全排列集合。例如给你[1,2,3],你要返回的是[[1,2,3],[1,3,2],[2,3,1],[2,1,3],[3,1,2],[3,2,1]]

思路:这个我想了很多，也尝试了很多，中间走的坑我就不说了，直接讲最后的结果吧，我是用的迭代，一列一列的写，写完一列，下一列继续按规律写，下图展示的是[1,2,3,4]的全排列（一行代表一组），以下图为例，我们可以看出几个规律：

1.全排列组合的个数就是给定的数的阶层。（如下图4!=24个）
2.倒数第三列以前就是给定的数的循环(图中有颜色的部分)。
3.没有了，用前两条就够了。

[1,2,3,4]的全排列

然后撸起袖子看代码(从注释下面的permute函数看起)：

    void newPermute(int* nums, int numsSize, int row, int col, int** result, int count) {
    if (numsSize == 1) {
        //只有一位
        result[row][col] = nums[0];
    }else {
        //还有好多位，需要继续迭代
        int newCount = numsSize-1;
        int divisor = count / numsSize;
        //遍历数组
        for(int i = 0; i < numsSize; i++){
            //赋值（有颜色的那部分）
            for (int j = 0;j < divisor; j++) {
                result[i*divisor+row+j][col] = nums[I];
            }
            //构造出新的需要全排列的集合
            int* tempResult = malloc(sizeof(int) * newCount);
            for (int k = 0; k < newCount; k++) {
                if (k < i) {
                    tempResult[k] = nums[k];
                }else {
                    tempResult[k] = nums[k+1];
                }
            }
            //调用递归(新的需要排列组合的集合，集合的个数，从第几行开始，从第几列开始，结果容器，总长度)
            newPermute(tempResult, newCount, i*divisor+row, col+1, result, divisor);
        }
    }
}
/**
 * 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) {
    //先利用第一条算出n！
    *returnSize = 1;
    for (int i = 2; i <= numsSize; i++) {
        *returnSize *= I;
    }
    //根据个数开辟空间，初始化容器
    int** result = malloc(sizeof(int*) * *returnSize);
    for (int i = 0; i < *returnSize; i++) {
        result[i] = malloc(sizeof(int) * numsSize);
    }
    //调用递归(参数含义依次是：新的需要排列组合的集合，集合的个数，从第几行开始，从第几列开始，结果容器，处理个数)
    newPermute(nums, numsSize, 0, 0, result, *returnSize);
    return result;
}

效率一般，然后和小伙伴们聊的时候发现C还是挺麻烦的，主要麻烦在需要处理内存，要开辟空间、要初始化，二维指针开辟完空间还要给一维空间开辟指针，分别初始化。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!