【题目】
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]
.
【分析】
这个题跟[LeetCode]46.Permutations非常类似,唯一的区别就是在这个题目中元素集合可以出现重复。这给我们带来一个问题就是如果不对重复元素加以区别,那么类似于{1,1,2}这样的例子我们会有重复结果出现。那么如何避免这种重复呢?方法就是对于重复的元素循环时跳过递归函数的调用,只对第一个未被使用的进行递归,我们那么这一次结果会出现在第一个的递归函数结果中,而后面重复的会被略过。如果第一个重复元素前面的元素还没在当前结果中,那么我们不需要进行递归。想明白了这一点,代码其实很好修改。首先我们要对元素集合排序,从而让重复元素相邻,接下来就是一行代码对于重复元素和前面元素使用情况的判断即可。
【代码】
/*********************************
* 日期:2015-01-19
* 作者:SJF0115
* 题目: 47.Permutations II
* 网址:https://oj.leetcode.com/problems/permutations-ii/
* 结果:AC
* 来源:LeetCode
* 时间复杂度:O(n!)
* 空间复杂度:O(n)
* 博客:
**********************************/
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > result;
if(num.empty()){
return result;
}//if
// 排序
sort(num.begin(),num.end());
bool visited[num.size()];
vector<int> visitedVec;
// 递归
DFS(num,visited,visitedVec,result);
return result;
}
private:
void DFS(vector<int> &num,bool visited[],vector<int> &visitedVec,vector<vector<int> > &result){
// 形成一个全排列
if(num.size() == visitedVec.size()){
result.push_back(visitedVec);
return;
}//if
for(int i = 0;i < num.size();++i){
// 重复元素
if(i > 0 && !visited[i-1] && num[i] == num[i-1]){
continue;
}//if
// 如果没有访问过
if(visited[i] == false){
visited[i] = true;
visitedVec.push_back(num[i]);
DFS(num,visited,visitedVec,result);
visitedVec.pop_back();
visited[i] = false;
}//if
}//for
}
};
int main(){
Solution solution;
vector<int> num;
num.push_back(1);
num.push_back(1);
num.push_back(2);
// 重新排列
vector<vector<int> > permutes = solution.permuteUnique(num);
// 输出
for(int i = 0;i < permutes.size();i++){
cout<<"[";
for(int j = 0;j < permutes[i].size();j++){
cout<<permutes[i][j];
}//for
cout<<"]"<<endl;
}
return 0;
}
【代码二】
/*********************************
* 日期:2015-01-19
* 作者:SJF0115
* 题目: 47.Permutations II
* 网址:https://oj.leetcode.com/problems/permutations-ii/
* 结果:AC
* 来源:LeetCode
* 时间复杂度:O(n!)
* 空间复杂度:O(n)
* 博客:
**********************************/
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > result;
if(num.empty()){
return result;
}//if
int count = num.size();
// 排序
sort(num.begin(),num.end());
// 统计每个元素的个数
map<int,int> countMap;
for(int i = 0;i < count;++i){
countMap[num[i]]++;
}//for
// 每个元素和出现次数复合绑定
vector<pair<int,int> > nums;
pair<int,int> pair;
for(int i = 0;i < count;++i){
pair.first = num[i];
pair.second = countMap[num[i]];
nums.push_back(pair);
}//for
vector<int> visited;
// 递归
DFS(nums,visited,result);
return result;
}
private:
void DFS(vector<pair<int,int> > &nums,vector<int> &visited,vector<vector<int> > &result){
// 形成一个全排列
if(nums.size() == visited.size()){
result.push_back(visited);
return;
}//if
int numCount = nums.size();
for(int i = 0;i < numCount;++i){
int count = 0;
// 重复元素不能重复打头
if(i > 0 && nums[i].first == nums[i-1].first){
continue;
}//if
int countVisit = visited.size();
// 统计重复元素已访问的个数
for(int j = 0;j < countVisit;++j){
if(visited[j] == nums[i].first){
count++;
}//if
}//for
// 如果还有元素没有访问过
if(count < nums[i].second){
visited.push_back(nums[i].first);
DFS(nums,visited,result);
visited.pop_back();
}//if
}//for
}
};
int main(){
Solution solution;
vector<int> num;
num.push_back(1);
num.push_back(2);
num.push_back(1);
// 重新排列
vector<vector<int> > permutes = solution.permuteUnique(num);
// 输出
for(int i = 0;i < permutes.size();i++){
cout<<"[";
for(int j = 0;j < permutes[i].size();j++){
cout<<permutes[i][j];
}//for
cout<<"]"<<endl;
}
return 0;
}
分享到:
相关推荐
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] ] 二.解题思路 主要是有两种...
题目来源:https://leetcode-cn.com/problems/permutations/ 题目 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,...
permutations2.py - 返回所有可能的唯一排列 3sum_2.py - 查找数组中所有唯一的三元组,其总和为零。 3sum.py - 查找数组中所有唯一的三元组,其总和为零。 first_last_pos_array.py - 找到给定目标值的开始和结束...
Source file for LeetCode Permutations Problem
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.cpp - kth_missing_number.cpp - 3sum2.cpp - 3sum.cpp - BST_from_preorder_traversal.cpp - 2sum.cpp - remove_adjacent_duplicates.cpp - 子集.cpp - 子集_2.cpp - Remove_Nth_Node_From_End_of_...
leetcode怎么计算空间复杂度是指 LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 already!) 我经常在递归的结束地方忘记return!!! 题型一:经典暴力递归:(里面涉及到重复不重复的...
leetcode Java 246 題目及解答 (英文) Contents 1 Rotate Array in Java 15 2 Reverse Words in a String II 19 3 Evaluate Reverse Polish Notation 21 4 Isomorphic Strings 25 5 Word Ladder 27 6 Word Ladder ...
leetcode 2 LeetCode - 30 Days 前言 相信所有写程式的人在面试前,总是在揣测在白板题会被问到什么问题,而我们最常听到的准备方式就是“刷”。上有数百个可能是面试官问你的题目,我把它...Permutations 目录 ref:
是时候回到Leetcode了2021-03-23 一些常用的内置函数: bin() :信息在collections.Counter :信息在itertools.permutations() :信息在记住,因为它在处理问题时确实可以提供帮助2021-03-24 开始处理HackerRank...
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、LeetCode 题解相关文章,至今收获不少好评。此仓库是公众号内容的补充,包括公众号文章涉及到的题目的参考代码,以及 ...
II 其他变种 编程之美 Preorder Traversal Inorder Traver sal postorder 非递归 不用栈! 字符串常用操作 字符串 各种转换 Pow(x,n) 优化 Permutations (交换 取子集两种方式) Trie树 11 中序遍历 无堆栈 (前序 ...
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 ...
permutations (normal and better), sum_3.py, unique_paths.py + unique_paths2.py, nQueens.py 很少包含外部库,所以下面的就可以了。 编译任何 C 程序: gcc -o X Xc 执行 python 脚本: chmod 755 X.py --> ....
2. combinations获取所有的组合情况,permutations可以获取所有的排列情况 3. 限制时间范围 4. 转化为字符型
All_Unique_Permutations Best_Time_To_Buy_And_Sell_Stocks_1 Best_Time_To_Buy_And_Sell_Stocks_2 Best_Time_To_Buy_And_Sell_Stocks_3 bst_Iterator 糖果 Character_Precedence Clone_Graph 组合_总和 Counting_...
Permutations II Combinations Letter Combinations of a Phone Number 广度优先搜索 Word Ladder Word Ladder II Surrounded Regions 总结 深度优先搜索 Additive Number Palindrome Partitioning Unique Paths ...