您的位置:首页 > 健康 > 美食 > 邯郸做网站优化_多少钱一度电_大连seo网站推广_现在疫情怎么样了最新消息

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

2024/12/5 21:36:16 来源:https://blog.csdn.net/weixin_48941116/article/details/143668765  浏览:    关键词:邯郸做网站优化_多少钱一度电_大连seo网站推广_现在疫情怎么样了最新消息
邯郸做网站优化_多少钱一度电_大连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 函数生成所有不重复排列。
    • 设置 returnSizereturnColumnSizes 用于返回结果。

复杂度分析

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com