邯郸做网站优化_多少钱一度电_大连seo网站推广_现在疫情怎么样了最新消息

题目描述

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

示例：

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

解题思路

1. 排序去重：先对数组 nums 进行排序，方便在递归生成排列时去重。
2. 回溯法生成排列：类似全排列问题（46题），使用回溯法，但在选择元素时，跳过重复的元素以避免重复排列。
3. 使用标记数组：使用一个布尔数组 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;
}

代码解析

1. 排序数组：

   qsort(nums, numsSize, sizeof(int), cmp);
   

   排序数组，使得相同的数字相邻，便于去重。

2. 跳过重复元素：

   if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
   

   • 当遇到重复元素时，只有在前一个相同元素已被使用的情况下才允许当前元素被选中。
   • 这确保了排列过程中不包含重复项。

3. 递归生成排列：

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

   • 使用 used 数组标记数字是否已被使用。
   • 每次递归生成完整排列时，调用 addResult 保存排列结果。

4. 主函数 permuteUnique：

   • 初始化结果数组 ResultArray，调用 backtrack 函数生成所有不重复排列。
   • 设置 returnSize 和 returnColumnSizes 用于返回结果。

复杂度分析

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