新博文地址:[leetcode]PermutationsII
Permutations II
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].
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
排列的题应该是很熟悉的,不熟悉的可以看这几道题:Permutations,Next Permutation, 其实,求排列的算法大致一样,这不过这道题要求可以有重复数字,求唯一的排列组合。
说起唯一,自然想起Set,我的算法也完全依赖于set,即,在生成排列序列的时候,先检查一下是否已经存在了,如果存在就不需要返回了。set的key很自然的选择用数组的String表达,遗憾的是,空间复杂度略大......
private String getString(List<Integer> list){ StringBuilder sb = new StringBuilder(); for(int i : list){ sb.append(i); } return sb.toString(); } public List<List<Integer>> permuteUnique(int[] num) { Set<String> set = new HashSet<String>(); List<List<Integer>> result = new ArrayList<List<Integer>>(); if (num == null || num.length == 0) { return result; } if (num.length == 1) { List<Integer> list = new ArrayList<Integer>(); list.add(num[0]); result.add(list); return result; } int[] pre = Arrays.copyOf(num, num.length - 1); List<List<Integer>> prePer = permuteUnique(pre); for (List<Integer> list : prePer) { for (int i = 0; i <= list.size(); i++) { List<Integer> newList = new ArrayList<Integer>(); for(int j = 0; j < i ;j ++){ newList.add(list.get(j)); } newList.add(num[num.length - 1]); for(int j = i; j < list.size(); j++){ newList.add(list.get(j)); } if(!set.contains(getString(newList))){ set.add(getString(newList)); result.add(newList); } } } return result; }
相关推荐
Source file for LeetCode Permutations Problem
c语言入门 C语言_leetcode题解之47-permutations-ii.c
js js_leetcode题解之47-permutations-ii.js
c语言入门 C语言_leetcode题解之46-permutations.c
js js_leetcode题解之46-permutations.js
LeetCode第46题,题目要求根据给定的整数集合,返回所有可能的排列组合。这个问题属于组合数学与算法设计的范畴,主要考察的是全排列的生成。 【解题思路】 1. **递归算法**:递归方法是从剩余未使用的元素中选择...
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 Python Go Solution Difficulty Tag 0017 Letter Combinations of a Phone Number Medium 回溯、暴力 0034...
- Permutations / Permutations II: 生成所有可能的排列组合,考虑重复元素的情况。 - Rotate Image: 给定一个二维矩阵,将它顺时针旋转90度。 - Group Anagrams: 组合所有字母异位词,即将字母顺序不同但字母组合...
leetcode怎么计算空间复杂度是指 LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 already!) 我经常在递归的结束地方忘记return!!! 题型一:经典暴力递归:(里面涉及到重复不重复的...
permutations2.py - 返回所有可能的唯一排列 3sum_2.py - 查找数组中所有唯一的三元组,其总和为零。 3sum.py - 查找数组中所有唯一的三元组,其总和为零。 first_last_pos_array.py - 找到给定目标值的开始和结束...
第47题"全排列II"(Permutations II)是LeetCode中的一道经典题目,它涉及到组合数学和递归的思想。在本题中,任务是找出所有可能的无重复字符的全排列。 全排列问题通常使用回溯法来解决,这是一种通过尝试所有...
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、LeetCode 题解相关文章,至今收获不少好评。此仓库是公众号内容的补充,包括公众号文章涉及到的题目的参考代码,以及 ...
leetcode 2 LeetCode - 30 Days 前言 相信所有写程式的人在面试前,总是在揣测在白板题会被问到什么问题,而我们最常听到的准备方式就是“刷”。上有数百个可能是面试官问你的题目,我把它...Permutations 目录 ref:
LeetCode 算法题解析 从给定的文件信息中,我们可以看到,这是一个关于 LeetCode 算法题的知识点总结。下面我们将对标题、描述、标签和部分内容进行详细的解析和总结。 标题:leetcode1-300.docx 这个标题表明了...
leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp - Detect_Pattern.cpp - degree_of_array.cpp - 键盘.cpp - 2Sum_Data_Structure_Design.cpp - shuffle_array.cpp - permutations.cpp - kth_missing_...
permutations import random import itertools import collections from fractions import Fraction from collections import Counter import operator import re from functools import reduce from collections ...
本资源包聚焦于LeetCode的第46题,名为"全排列"(Permutations)。这道题目要求我们找到所有可能的排列方式,对于一个给定的没有重复数字的数组。解这类问题,我们可以使用回溯法或者深度优先搜索(DFS)策略来完成...