The Unique Permutations Algorithm with Duplicate Elements
- 时间:2020-09-17 14:26:24
- 分类:网络文摘
- 阅读:80 次
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
1 2 3 4 5 [ [1,1,2], [1,2,1], [2,1,1] ][ [1,1,2], [1,2,1], [2,1,1] ]
How to Get Unique Permuations in C++?
In fact, the C++ STL algorithm header provides the std::next_permutation() which deals with the duplicate elements in the candidate array. We just need to sort the array, then start permutating until the next_permutation() returns false.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> r; sort(begin(nums), end(nums)); r.push_back(nums); while (next_permutation(begin(nums), end(nums))) { r.push_back(nums); } return r; } }; |
class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> r; sort(begin(nums), end(nums)); r.push_back(nums); while (next_permutation(begin(nums), end(nums))) { r.push_back(nums); } return r; } };
Recursive Permutation Algorithm without Duplicate Result
Similar to The Permutation Algorithm for Arrays using Recursion, we can do this recursively by swapping two elements at each position. However, we need to keep tracking of the solution that has also been in the permutation result using a hash set.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> r; dfs(nums, 0, r, ""); return r; } private: unordered_set<string> used; void dfs(vector<int>& nums, int index, vector<vector<int>> &r, string key) { if (index == nums.size()) { if (!used.count(key)) { r.push_back(nums); used.insert(key); } } else { for (int i = index; i < nums.size(); ++ i) { swap(nums[i], nums[index]); dfs(nums, index + 1, r, key + std::to_string(nums[index])); swap(nums[i], nums[index]); } } } }; |
class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> r; dfs(nums, 0, r, ""); return r; } private: unordered_set<string> used; void dfs(vector<int>& nums, int index, vector<vector<int>> &r, string key) { if (index == nums.size()) { if (!used.count(key)) { r.push_back(nums); used.insert(key); } } else { for (int i = index; i < nums.size(); ++ i) { swap(nums[i], nums[index]); dfs(nums, index + 1, r, key + std::to_string(nums[index])); swap(nums[i], nums[index]); } } } };
In the worst cases, both implementations are O(N!) as N! is the total number of permutation results for N-size elements.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:Join this Niche: Inspirational Charitable and Non-Profit Blogs 7 Passive Income Ideas to Complement Your Blog Funny YouTuber Creates Device to Shoot Facemasks To Your Face YouTube’s New “Viewer Applause” Feature Provides Revenue for Blo Taiwanese Instagram Grandparents Prove Blogging and Social Media These Incredible Hologram Machines Could Change the Vlogging Gam Prepare All Keyboard Warriors: A TikTok and Twitter Merger is Ab Content Creation Platforms That Pay in Crypto How to be like Elon Musk: An Influencer CEO Your Simple Guide to Ultimate Technology Stack Every Blogger Nee
- 评论列表
-
- 添加评论