题解55 | 元素影重重#集合的所有子集(一)(二)#
集合的所有子集(二)
https://www.nowcoder.com/practice/a3dfd4bc8ae74fad9bc65d5ced7ae813
一、现在有一个没有重复元素的整数集合S,求S的所有子集注意:你给出的子集中的元素必须按升序排列
给出的解集中不能出现重复的元素
#include <algorithm> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param S int整型vector * @return int整型vector<vector<>> */ vector<vector<int> > subsets(vector<int>& S) { // write code here 迭代 vector<vector<int>> ans; ans.push_back({}); for (int i = 0; i < S.size(); i++) { int size = ans.size(); for (int j = 0; j < size; j++) { vector<int> row(ans[j]); row.push_back(S[i]); sort(row.begin(), row.end()); ans.push_back(row); } } //sort(ans.begin(), ans.end()); return ans; } };
算法基本思想:
利用迭代的方式,每次将一个新的元素加入到已有的子集中,生成新的子集。
时间复杂度:
O(2^n * nlogn),其中n为数组S的长度,2^n为所有子集的个数,nlogn为每次加入新元素时需要排序的时间复杂度。
空间复杂度:
O(2^n * n),需要存储所有子集的空间。
二、现在有一个整数集合S,里面可能存在重复的元素(在一的基础上加栈去重)
#include <algorithm> #include <stack> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型vector<vector<>> */ vector<vector<int> > subsets(vector<int>& nums) { // write code here vector<vector<int>> ans; ans.push_back({}); for (int i = 0; i < nums.size(); i++) { int size = ans.size(); for (int j = 0; j < size; j++) { vector<int> row(ans[j]); row.push_back(nums[i]); sort(row.begin(), row.end()); ans.push_back(row); } } //前面的就是集合的所有子集(一) //加个数组栈去重一下就好了 stack<vector<int>> s; sort(ans.begin(), ans.end()); for (int i = 0; i < ans.size(); i++) { if (s.empty() || s.top() != ans[i]) { s.push(ans[i]); } } vector<vector<int>> ans2; while (!s.empty()) { ans2.push_back(s.top()); s.pop(); } sort(ans2.begin(), ans2.end()); return ans2; } };
算法基本思想:
利用迭代的方式,每次将一个新的元素加入到已有的子集中,生成新的子集。然后使用一个栈去重。
时间复杂度:
O(2^n * nlogn),其中n为数组nums的长度,2^n为所有子集的个数,nlogn为每次加入新元素时需要排序的时间复杂度。
空间复杂度:
O(2^n * n),需要存储所有子集的空间。
2024考研数据结构 文章被收录于专栏
本人考研刷算法题,立此专栏练习强化。