给出一组数字,返回该组数字的所有排列
例如:
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
(以数字在数组中的位置靠前为优先级,按字典序排列输出。)
[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]
[[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; }