韩国大型门户网站,潼南县大潼建设有限公司网站,seo长尾关键词优化,摄影摄像网站建设题目描述 题目分析
感觉这道题让自己对枚举排列有了一个更好的认识#xff0c;感觉自己的这种思路不错。
假设没有重复元素#xff08;退化成78.子集#xff09;#xff0c;我们应该怎么做#xff1f;初始的时候幂集中只有一个空集#xff0c;然后对每个元素#xff0…题目描述 题目分析
感觉这道题让自己对枚举排列有了一个更好的认识感觉自己的这种思路不错。
假设没有重复元素退化成78.子集我们应该怎么做初始的时候幂集中只有一个空集然后对每个元素我们添加给幂集中的每个元素这样进行一遍遍历复杂度是O(1)O(2)O(4)...O(2n−1)O(2n)O(1)O(2)O(4)...O(2^{n-1})O(2^n)O(1)O(2)O(4)...O(2n−1)O(2n)
对于有重复元素的我们应该如何处理呢不难发现假设我们把重复元素放在一起则对于第一个元素是没有什么影响的但是对第二个元素开始我们对幂集最前面集合添加元素和前面的那个元素没有区别因此就会出现重复从哪里开始不一样呢从前一个元素开始添加的部分开始因此我们用一个变量记录前一个元素开始添加的位置然后从重复元素的第二个开始都从前一个元素添加的开始位置开始添加最后更新这个变量。可以再对照代码理解一下代码比较简单
class Solution {
public:vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(), nums.end());vectorvectorint ans;ans.push_back(vectorint());ans.push_back(vectorint());ans.back().push_back(nums[0]);int n nums.size();int pre_i 1; //保存上次添加后的起始地址for(int i 1; i n; i) {int m ans.size();int j 0;if (nums[i] nums[i - 1]) {//如果和上一个数字一样则从上一个数字开始的地方开始因为前面的已经由上一个数字处理过了j pre_i;}for (; j m; j) {auto t ans[j];t.push_back(nums[i]);ans.push_back(t);}pre_i m; //更新per_i}return ans;}
};吐槽
觉得子集的思路比题解的要清晰复杂度应该也低很多我这个应该是O(2n)O(2^n)O(2n)不知道为什么题解的那么复杂要枚举二进制或者用回溯。 这个执行用时有点玄学的可能只测试了部分样例吧毕竟是企业少测试一会就可以多赚钱可以理解。我觉得leetcode还是比较适合用来学习算法和数据结构的感觉写官方题解的人的水平也不一样有的题解思路清晰代码巧妙能从代码中看出写这个代码的人造诣很高对语言的理解也很深刻但是今天的这个题解我就觉得不怎么样子集那道题的题解我也觉得不怎么样复杂度感觉都求错了。
