当前位置：首页 > news >正文

力扣第47题“全排列 II”

news 2024/11/14 14:47:46

题目描述

给定一个可能包含重复元素的整数数组 nums，返回所有不重复的排列。

示例：

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

解题思路

排序去重：先对数组 nums 进行排序，方便在递归生成排列时去重。
回溯法生成排列：类似全排列问题（46题），使用回溯法，但在选择元素时，跳过重复的元素以避免重复排列。
使用标记数组：使用一个布尔数组 used 来标记元素是否被选择过。对于相邻的重复元素，若前一个相同元素未被使用，则跳过当前元素，以保证生成的排列不重复。

代码实现

以下是详细的代码实现及逐行注释：

#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++;
}// 比较函数，用于排序
int cmp(const void* a, const void* b) {return *(int*)a - *(int*)b;
}// 递归函数生成排列
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 (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;if (!used[i]) {  // 选择一个未使用的数字used[i] = true;permutation[level] = nums[i];backtrack(nums, numsSize, permutation, level + 1, used, result);  // 递归used[i] = false;  // 回溯}}
}// 主函数
int** permuteUnique(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));// 排序数组，便于去重处理qsort(nums, numsSize, sizeof(int), cmp);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, 1, 2};int numsSize = sizeof(nums) / sizeof(nums[0]);int returnSize;int* returnColumnSizes;int** result = permuteUnique(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;
}

代码解析

排序数组：
```
qsort(nums, numsSize, sizeof(int), cmp);
```
排序数组，使得相同的数字相邻，便于去重。
跳过重复元素：
```
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
```
- 当遇到重复元素时，只有在前一个相同元素已被使用的情况下才允许当前元素被选中。
- 这确保了排列过程中不包含重复项。
递归生成排列：
```
void backtrack(int* nums, int numsSize, int* permutation, int level, bool* used, ResultArray* result)
```
- 使用 used 数组标记数字是否已被使用。
- 每次递归生成完整排列时，调用 addResult 保存排列结果。
主函数 permuteUnique：
- 初始化结果数组 ResultArray，调用 backtrack 函数生成所有不重复排列。
- 设置 returnSize 和 returnColumnSizes 用于返回结果。