力扣第46题“全排列”

题目描述

给定一个没有重复数字的整数数组 nums，返回其所有可能的排列。

示例：

输入: nums = [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解题思路

1. 回溯法：通过递归构建排列，每次选择一个未使用的数字添加到当前排列中。
2. 使用数组标记已选数字：使用一个布尔数组 used 来标记某个元素是否已被使用。
3. 递归和回溯：每次添加一个新的数字到排列中，递归地继续添加直到形成完整排列，再回溯到上一状态尝试其他可能性。

代码实现

下面是详细的代码实现。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int** data;       // 存储所有排列结果
    int* columnSizes; // 每个排列的长度
    int size;         // 当前排列的数量
    int capacity;     // 容量
} ResultArray;

// 初始化结果数组
ResultArray* createResultArray(int capacity) {
    ResultArray* result = (ResultArray*)malloc(sizeof(ResultArray));
    result->data = (int**)malloc(capacity * sizeof(int*));
    result->columnSizes = (int*)malloc(capacity * sizeof(int));
    result->size = 0;
    result->capacity = capacity;
    return result;
}

// 添加排列到结果数组
void addResult(ResultArray* result, int* permutation, int length) {
    if (result->size >= result->capacity) {
        result->capacity *= 2;
        result->data = (int**)realloc(result->data, result->capacity * sizeof(int*));
        result->columnSizes = (int*)realloc(result->columnSizes, result->capacity * sizeof(int));
    }
    result->data[result->size] = (int*)malloc(length * sizeof(int));
    for (int i = 0; i < length; i++) {
        result->data[result->size][i] = permutation[i];
    }
    result->columnSizes[result->size] = length;
    result->size++;
}

// 递归函数生成排列
void backtrack(int* nums, int numsSize, int* permutation, int level, bool* used, ResultArray* result) {
    if (level == numsSize) {  // 生成完整排列
        addResult(result, permutation, numsSize);
        return;
    }
    
    for (int i = 0; i < numsSize; i++) {
        if (!used[i]) {  // 选择一个未使用的数字
            used[i] = true;
            permutation[level] = nums[i];
            backtrack(nums, numsSize, permutation, level + 1, used, result);  // 递归
            used[i] = false;  // 回溯
        }
    }
}

// 主函数
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    ResultArray* result = createResultArray(100); // 初始化结果数组
    int* permutation = (int*)malloc(numsSize * sizeof(int));
    bool* used = (bool*)calloc(numsSize, sizeof(bool));
    
    backtrack(nums, numsSize, permutation, 0, used, result);
    
    *returnSize = result->size;
    *returnColumnSizes = result->columnSizes;
    free(permutation);
    free(used);
    return result->data;
}

// 测试代码
int main() {
    int nums[] = {1, 2, 3};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int returnSize;
    int* returnColumnSizes;
    
    int** result = permute(nums, numsSize, &returnSize, &returnColumnSizes);
    
    printf("所有排列结果:\n");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(", ");
        }
        printf("]\n");
        free(result[i]);
    }
    
    free(result);
    free(returnColumnSizes);
    return 0;
}

代码解析

1. 定义结果数组结构体：

   • ResultArray 结构体用于存储所有排列及其相关信息，包含每个排列的长度和排列结果的指针。

2. 初始化结果数组：

   ResultArray* createResultArray(int capacity)
   

   用于初始化 ResultArray 结构体，分配初始容量为 100 的空间。

3. 添加排列到结果数组：

   void addResult(ResultArray* result, int* permutation, int length)
   

   将生成的排列添加到 ResultArray 中，当数组满时进行扩容。

4. 回溯函数 backtrack：

   void backtrack(int* nums, int numsSize, int* permutation, int level, bool* used, ResultArray* result)
   

   • 使用 level 表示当前排列的层级。
   • used 数组用于标记哪些数字已被使用，避免重复。
   • 每次递归生成完整排列时，调用 addResult 保存结果。

5. 主函数 permute：

   int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
   

   • 初始化 ResultArray 结构体，调用 backtrack 函数生成排列。
   • 设置 returnSize 和 returnColumnSizes，用于返回结果。

复杂度分析

• 时间复杂度：O(n * n!)，其中 n 为数组长度。生成的排列数量为 n!，每个排列的生成需要 O(n) 的时间。
• 空间复杂度：O(n * n!)，存储所有排列结果的空间复杂度。

原文地址：https://blog.csdn.net/weixin_48941116/article/details/143644711

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！