博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Permutations I II@LeetCode
阅读量:6096 次
发布时间:2019-06-20

本文共 1643 字,大约阅读时间需要 5 分钟。

递归的方法,设置一个used数组,用来记录相应位置是否已经使用过了,然后设置一个permutation数组,用来保存当前的序列,如果当前序列长度到达额定长度后,将该序列加入最后结果集合中。

实现代码:

javapublic class Solution {    public List
> permute(int[] num) { List
> result = new ArrayList
>(); generate(num, new boolean[num.length], result, new ArrayList
()); return result; } private void generate(int[] num, boolean[] used, List
> result, List
permutation) { if (permutation.size() == num.length) { result.add(new ArrayList
(permutation)); } else { for (int i = 0; i < num.length; i++) { if (!used[i]) { permutation.add(num[i]); used[i] = true; generate(num, used, result, permutation); permutation.remove(permutation.size() - 1); used[i] = false; } } } }}

难度的提升在于:有数字是重复的。

针对这一点,可以先对原始数据集合进行排序,这样保证了如果有重复元素,那么他们也是相邻的。同时,在递归函数中,同一层递归中,除了判断该位有没有使用过,还要判断当前位之后的元素是否与当前位相同,如果相同则要一直往前找到第一个不相同的且没有使用过的元素,作为下一个当前位插入permutation数组中。

实现代码:

javapublic class Solution {    public List
> permuteUnique(int[] num) { List
> result = new ArrayList
>(); Arrays.sort(num); generate(num, new boolean[num.length], result, new ArrayList
()); return result; } private void generate(int[] num, boolean[] used, List
> result, List
permutation) { if (permutation.size() == num.length) { result.add(new ArrayList
(permutation)); } else { int i = 0; while (i < used.length) { if (!used[i]) { permutation.add(num[i]); used[i] = true; generate(num, used, result, permutation); permutation.remove(permutation.size() - 1); used[i] = false; while (i < used.length - 1 && num[i] == num[i + 1]) { i++; } } i++; } } }}

转载地址:http://zxwza.baihongyu.com/

你可能感兴趣的文章
深入python的set和dict
查看>>
C++ 11 lambda
查看>>
Hadoop2.5.0 搭建实录
查看>>
实验吧 recursive write up
查看>>
High-speed Charting Control--MFC绘制图表(折线图、饼图、柱形图)控件
查看>>
go test命令參数问题
查看>>
linux 搜索文本
查看>>
超实用Mac软件分享(二)
查看>>
Android JSON数据解析
查看>>
DEV实现日期时间效果
查看>>
java注解【转】
查看>>
Oracle表分区
查看>>
centos 下安装g++
查看>>
调试、手机-手游开发知识(三)--NDK联机调试-by小雨
查看>>
嵌入式,代码调试----GDB扫盲
查看>>
类斐波那契数列的奇妙性质
查看>>
配置设置[Django]引入模版之后报错Requested setting TEMPLATE_DEBUG, but settings are not configured....
查看>>
下一步工作分配
查看>>
Response. AppendHeader使用大全及文件下载.net函数使用注意点(转载)
查看>>
Wait Functions
查看>>