给出一组可能包含重复项的数字,返回该组数字的所有排列。结果以字典序升序排列。
数据范围: ,数组中的值满足
要求:空间复杂度 ,时间复杂度
int CMPnumLen; 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 cmpArr(const void *a, const void *b) { int i=0; while(i<CMPnumLen) { if((*(int**)a)[i] > (*(int**)b)[i]) return 1; else if((*(int**)a)[i] < (*(int**)b)[i]) return -1; else i++; } return 0; } int** permuteUnique(int* num, int numLen, int* returnSize, int** returnColumnSizes ) { int **permuteres, **res, i, NewReturnSize=0; permuteres = propermute(num, numLen); *returnSize = 1; for(i=1; i<=numLen; i++) (*returnSize) *= i; CMPnumLen = numLen; qsort(permuteres, *returnSize, sizeof(int*), cmpArr); res = (int**)malloc(*returnSize*sizeof(int*)); res[0] = (int*)malloc(numLen*sizeof(int)); memcpy(res[0], permuteres[0], numLen*sizeof(int)); NewReturnSize++; for(i=1; i<*returnSize; i++) { if(memcmp(res[NewReturnSize-1], permuteres[i], numLen*sizeof(int))!=0) { res[NewReturnSize] = (int*)malloc(numLen*sizeof(int)); memcpy(res[NewReturnSize], permuteres[i], numLen*sizeof(int)); NewReturnSize++; } } *returnSize = NewReturnSize; *returnColumnSizes = (int*)malloc((*returnSize)*sizeof(int)); for(i=0; i<(*returnSize); i++) (*returnColumnSizes)[i] = numLen; return res; }