没有重复项数字的全排列

[编程题]没有重复项数字的全排列

热度指数：74582 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一组数字，返回该组数字的所有排列

例如：

[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数 $0 < n \le 6$

要求：空间复杂度 $O(n!)$ ，时间复杂度 $O(n!）$

示例1

输入

[1,2,3]

输出

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2

输入

[1]

输出

[[1]]

算法知识视频讲解

一个优雅的程序猿

#include <string.h>
int** propermute(int* num, int numLen) {
    int **res, **lastres, returnSize, i, j;
    returnSize = 1;
    for(i=1; i<=numLen; i++) 
        returnSize *= i;
    if(numLen==0) 
        return NULL;
    res = (int**)malloc(returnSize*sizeof(int*));
    for(i=0; i<returnSize; i++) 
        res[i] = (int*)malloc(numLen*sizeof(int));
    if(numLen==1) {
        res[0][0] = num[0];
        return res;
    }
    lastres = propermute(num+1, numLen-1);
    for(i=0; i<returnSize/numLen; i++) {
        for(j=0; j<numLen; j++) {
            memcpy(res[i*numLen+j], lastres[i], j*sizeof(int));
            res[i*numLen+j][j] = num[0];
            memcpy(res[i*numLen+j]+j+1, lastres[i]+j, (numLen-j-1)*sizeof(int));
        }
    }
    return res;
}
int** permute(int* num, int numLen, int* returnSize, int** returnColumnSizes ) {
    int **res, i;
    *returnSize = 1;
    for(i=1; i<=numLen; i++) 
        (*returnSize) *= i;
    *returnColumnSizes = (int*)malloc((*returnSize)*sizeof(int));
    for(i=0; i<(*returnSize); i++) 
        (*returnColumnSizes)[i] = numLen;
    res = propermute(num, numLen);
    return res;
}

编辑于 2024-03-22 12:12:45 回复(0)

ada_lsj

void swap(int *a, int *b)

{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void dfs(int* num, int index, int numLen, int* returnSize, int** returnColumnSizes, int **ret)
{
int j = 0;
if (index == numLen) {
ret[*returnSize] = (int *)malloc(numLen * sizeof(int));
for (j = 0; j < numLen; j++) {
ret[*returnSize][j] = num[j];
}
(*returnColumnSizes)[*returnSize] = numLen;
(*returnSize)++;
return;
}

for (j = index; j < numLen; j++) {
swap(&num[j], &num[index]);
dfs(num, index+1, numLen, returnSize, returnColumnSizes, ret);
swap(&num[j], &num[index]);
}
return;
}
int** permute(int* num, int numLen, int* returnSize, int** returnColumnSizes ) {
// write code here
*returnColumnSizes = (int*)malloc(sizeof(int) * 100001);
int **ret = (int**)malloc(sizeof(int*) * 100001);
*returnSize = 0;
dfs(num, 0, numLen, returnSize, returnColumnSizes, ret);

return ret;
}

发表于 2022-05-15 10:41:46 回复(3)