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

LeetCode【0047】全排列II

本文目录

  • 1 中文题目
  • 2 求解方法:回溯法
    • 2.1 方法思路
    • 2.2 Python代码
    • 2.3 复杂度分析
  • 3 题目总结

1 中文题目

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

示例:

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

提示:

  • 1 ≤ n u m s . l e n g t h ≤ 8 1 \leq nums.length \leq 8 1nums.length8
  • − 10 ≤ n u m s [ i ] ≤ 10 -10 \leq nums[i] \leq 10 10nums[i]10

2 求解方法:回溯法

2.1 方法思路

方法核心

通过回溯法实现所有可能的排列,使用交换元素的方式进行排列生成,在每一层递归中使用集合记录已经使用过的数字来避免重复,同时通过预先排序来确保相同数字的相对位置固定,从而保证不会生成重复的排列。

实现步骤

(1)预处理阶段:

  • 对输入数组进行排序,使相同的数字相邻
  • 初始化结果列表用于存储所有合法排列
  • 获取输入数组的长度

(2)回溯函数设计:

  • 定义参数first表示当前要填充的位置
  • 在每一层递归中维护一个used集合记录已使用的数字
  • 通过交换元素的方式生成不同的排列
  • 使用集合去重来避免同一层使用相同的数字

(3)去重策略:

  • 在每一层递归中使用集合记录已经在该位置使用过的数字
  • 如果某个数字在当前层已经使用过,则跳过
  • 通过预排序确保相同数字的相对顺序不变

(4)状态恢复:

  • 在递归返回前将交换的元素换回原位
  • 保证不影响后续的排列生成

方法示例
以输入 nums = [1,1,2] 为例:

初始状态:
nums = [1,1,2](已排序)
result = []递归过程详解:1. first = 0:used = set()1.1 i = 0: nums[0] = 1used = {1}交换后:[1,1,2]递归到first = 11.1.1 used = set()i = 1: nums[1] = 1used = {1}交换后:[1,1,2]递归到first = 21.1.1.1 used = set()i = 2: nums[2] = 2used = {2}交换后:[1,1,2]递归到first = 3添加排列[1,1,2]恢复:[1,1,2]恢复:[1,1,2]恢复:[1,1,2]1.2 i = 1: nums[1] = 11在used中,跳过1.3 i = 2: nums[2] = 2used = {1,2}交换后:[2,1,1]递归到first = 1... (类似过程)最终添加排列[2,1,1]恢复:[1,1,2]最终结果:
result = [[1,1,2], [1,2,1], [2,1,1]]

2.2 Python代码

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:# 结果列表result = []n = len(nums)# 先对数组排序,方便后续去重nums.sort()def backtrack(first = 0):# 如果已经到达数组末尾,说明找到了一个排列if first == n:result.append(nums[:])return# 用于记录当前层使用过的数字used = set()# 尝试将每个数字放到当前位置for i in range(first, n):# 如果当前数字已经在当前层使用过,则跳过if nums[i] in used:continue# 将当前数字加入已使用集合used.add(nums[i])# 交换当前数字到待填充位置nums[first], nums[i] = nums[i], nums[first]# 递归处理下一个位置backtrack(first + 1)# 回溯,恢复原状nums[first], nums[i] = nums[i], nums[first]# 开始回溯backtrack()return result

2.3 复杂度分析

  • 时间复杂度:O(n!)
    • 对于n个不同的数字,有n!种排列
    • 对于有重复数字的情况,排列数会少于n!
    • 每个排列需要O(n)的时间来复制到结果集
    • 排序需要O(nlogn)的时间,但这不是主导项
  • 空间复杂度:O(n)
    • 递归调用栈的深度为O(n)
    • 每层递归中的used集合大小最大为O(n)

3 题目总结

题目难度:中等
数据结构:数组
应用算法:回溯法


http://www.mrgr.cn/news/74833.html

相关文章:

  • 基于STM32的智能家居安防系统设计
  • 工作和学习遇到的技术问题
  • SpringBoot单体服务无感更新启动,动态检测端口号并动态更新
  • 【MySQL】MySQL函数之JSON_EXTRACT
  • Vue Cli的配置中configureWebpack和chainWebpack的主要作用及区别是什么?
  • 【 ElementUI 组件Steps 步骤条使用新手详细教程】
  • HarmonyOS基础:选项卡组件(Tabs)
  • PostgreSQL 查看重复索引
  • 第一课-Rust入门
  • 数据结构查找-哈希表(创建+查找+删除)+(C语言代码)
  • Tofu识别跟踪变焦镜头控制接口与协议
  • 云服务器安装mysql8.0(阿里云或者腾讯云都可以)
  • 比高考还严?该地软考报考减少了5420人,工作人员却增加100多人!
  • 如何使用Jupyter
  • 【机器学习chp2】贝叶斯最优分类器、概率密度函数的参数估计、朴素贝叶斯分类器、高斯判别分析。万字超详细分析总结与思考
  • 真的别跟风了!PMP认证原来只对这些人有用...
  • leveldb存储token的简单实现
  • 理解 C++ 中的 `const` 关键字
  • 域名绑定服务器小白教程
  • [刷题]入门1.矩阵转置
  • MATLAB和Python及R瑞利散射
  • 37邮件服务器
  • Sorvall Legend Micro 17 微量离心机产品特性
  • 开放式耳机怎么戴?不入耳的蓝牙耳机推荐
  • 背景移除,主体物抠图模型 RMBG-2.0:最佳一键去背景模型
  • 独孤思维:负债,入不敷出,要不要投资做副业