没有重复项数字的全排列

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

热度指数：83191 时间限制：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 <stdio.h>
#include <stdlib.h>
#include <string.h>
int flag=0;
void swap(int* a, int* b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
void func(int* num,int numLen, int k, int** retNum){
    if (k == numLen) {
        retNum[flag] = (int*) malloc(sizeof(int) * numLen); 
        for (int j = 0; j<numLen; j++) {
            retNum[flag][j] = num[j];
        }
        flag++;
        return ;
    }
    
    for (int i = k; i<numLen; i++) {
        swap(&num[i], &num[k]);
        func(num, numLen, k+1, retNum);
        swap(&num[i], &num[k]);
    }
    return ;
}
int** permute(int* num, int numLen, int* returnSize, int** returnColumnSizes ) {
    // write code here
    int ret = 0;
    int k = numLen;
    *returnSize = 1;
    int tmp;
    for (int i = 1; i <= numLen; i++) {
        *returnSize = *returnSize * i;
    }
    int** retNum = (int**)malloc(sizeof(int*) * (*returnSize));
    *returnColumnSizes = (int*)malloc((*returnSize)*sizeof(int));
    for(int i=0; i<(*returnSize); i++) 
        (*returnColumnSizes)[i] = numLen;
    func(num, numLen, 0, retNum);

    for (int i = 0; i < *returnSize; i++) {
        for (int j = i+1; j < *returnSize; j++) {
            for (int k = 0; k < numLen; k++) {
                if (retNum[i][k] == retNum[j][k]) {
                    continue;
                }
                if (retNum[i][k] < retNum[j][k]) {
                    break;
                }
                if (retNum[i][k] > retNum[j][k]) {
                    for (int a = 0; a < numLen; a++) {
                        tmp = retNum[i][a];
                        retNum[i][a] = retNum[j][a];
                        retNum[j][a] = tmp;
                    }
                    break;
                }
            }
        }
    }
    
    return retNum;
}

发表于 2024-10-13 21:24:25 回复(0)

一个优雅的程序猿

#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)