- 浏览: 173106 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
与Permutations 这道题不同的是数组中包含重复的元素,有重复的元素我们就不能通过值来判断当前元素是否已经被记录,我们可以通过下标来记录元素是否被记录,因为每个元素的下标是唯一的,这是我们用一个辅助数组isVisited来记录,并且isVisited要同结果集一同回溯。此外数组中可能包含很多重复元素,因此我们可以先将数组排序,然后在回溯时,记录删除的元素,当回溯后继续往前走时,首先判断当前元素与之前删除的元素是否相同,如果相同就直接跳过。代码如下:
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
与Permutations 这道题不同的是数组中包含重复的元素,有重复的元素我们就不能通过值来判断当前元素是否已经被记录,我们可以通过下标来记录元素是否被记录,因为每个元素的下标是唯一的,这是我们用一个辅助数组isVisited来记录,并且isVisited要同结果集一同回溯。此外数组中可能包含很多重复元素,因此我们可以先将数组排序,然后在回溯时,记录删除的元素,当回溯后继续往前走时,首先判断当前元素与之前删除的元素是否相同,如果相同就直接跳过。代码如下:
public class Solution { public List<List<Integer>> permuteUnique(int[] nums) { ArrayList<Integer> list = new ArrayList<Integer>(); ArrayList<List<Integer>> llist = new ArrayList<List<Integer>>(); ArrayList<Integer> isVisited = new ArrayList<Integer>(); if(nums == null || nums.length == 0) return llist; java.util.Arrays.sort(nums); getPermute(0, nums, isVisited, list, llist); return llist; } public void getPermute(int start, int[] nums, ArrayList<Integer> isVisited, ArrayList<Integer> list, ArrayList<List<Integer>> llist) { if(list.size() == nums.length) { if(!llist.contains(list)) llist.add(new ArrayList<Integer>(list)); } int former = Integer.MIN_VALUE; for(int i = start; i < nums.length; i++) { if(former == nums[i]) continue; if(!isVisited.contains(i)) { list.add(nums[i]); isVisited.add(i); getPermute(0, nums, isVisited, list, llist); former = list.remove(list.size() - 1); isVisited.remove(isVisited.size() - 1); } } } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 224Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 222You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 330Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 448Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 427Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 425The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 383Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 514Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 879Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 552Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 598Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 761Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 731You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For a undirected graph with tre ...
相关推荐
235 Permutations II 571 236 Permutation Sequence 573 237 Generate Parentheses 575 238 Combination Sum 577 239 Combination Sum II 579 240 Combination Sum III 581 241 Combinations 583 242 Letter ...
Permutations II Combinations Letter Combinations of a Phone Number 广度优先搜索 Word Ladder Word Ladder II Surrounded Regions 总结 深度优先搜索 Additive Number Palindrome Partitioning Unique Paths ...
Richard P. Stanley的经典文章A Survey of Alternating Permutations,供有需要者下载
Permutations are ubiquitous in many real-world problems, such as voting, ranking, and data association. Representing uncertainty over permutations is challenging, since there are n! possibilities, and...
Permutations Medium 回溯 0047 Permutations II Medium 递归、回溯 0051 N-Queens Hard 回溯 0053 Maximum Subarray Easy 动态规划 0069 Sqrt(x) Easy 二分、牛顿迭代 0070 Climbing Stairs Easy 动态规划 0075 ...
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、LeetCode 题解相关文章,至今收获不少好评。...Permutations全排列 Permutations II全排列 II Maximum Suba
046:Permutations 047:Permutations II 051:N-Queens 052:N-Queens II 071: Letter Combinations of a Phone Number 093:Restore IP Addresses 树的遍历问题也可以用这种思想来解释。只不过是特殊的递归而已。...
安装$ npm install --save permutations-count 用法 var permutationsCount = require ( 'permutations-count' ) ;var numPermutations = permutationsCount ( 12 , 3 ) ;console . log ( numPermutations ) ; // =>...
Chapter1PermutationsandCombinations排列和组合.pdf
排列
数字排列重复数排列Расчётколичествастроквфайлепроизвёлкомандой:.. \ permutations.txt“ |测量对象-线ВWindouse 标题:行字字符属性30240
信息安全_数据安全_Lossy_Trapdoor_Permutations_with 事件检测 定向攻击 常规渗透 移动安全 事件检测
permutations ( 'abc' ) // [ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]permutations ( 'ab' ) // [ 'ab', 'ba']permutations ( 'aa' ) // [ 'aa', 'aa' ]permutations ( 'aa' , { unique : true } ) // [ 'aa' ]...
大师Donald E. Knuth(汉名高德纳)的著作,计算机程序设计与艺术第四卷3册:生成所有组合和分划Generating All Combinations and Permutations(中英)
Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 二.解题思路 主要是有两种...
资源分类:Python库 所属语言:Python 资源全名:email_permutations-0.2.0-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
大师Donald E. Knuth(汉名高德纳)的著作,计算机程序设计与艺术第四卷2册:生成所有元组和排列Generating All Tuples and Permutations(中英)
D型排列上的超越数,赵飞燕,,本文主要研究了B型超越数,稳定点和圈在D型排列上的分布。我们得到了带符号的超越数在D型排列和D型错排上的递推关系和闭公式。