面试题 08.04. 幂集
2021/9/28 23:10:49
本文主要是介绍面试题 08.04. 幂集,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
幂集。编写一种方法,返回某集合的所有子集。集合中不包含重复的元素。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
解题思路
1.使用循环
代码思路:
- 每次将res中已存在的List进行复制一份,并将参数中的一个元素添加到每个复制的List中
- 第一步放一个【】空的List进入res中
- 第二次拷贝空的List【】,并放入一个nums形参中的值1,现在res中有【【】,【1】】
- 第三次重复上次的操作,在放入nums中另一个值,res有【【】,【1】,【2】,【1,2】】
- 第三次res中有【【】,【1】,【2】,【1,2】,【3】,【1,3】,【2,3】,【1,2,3】】
代码:
class Solution { public static void main(String[] args) { Solution solution = new Solution(); List<List<Integer>> subsets = solution.subsets(new int[]{1, 2, 3}); System.out.println(subsets.toString()); } public List<List<Integer>> subsets(int[] nums) { if (nums.length == 0) { return new ArrayList<>(); } List<List<Integer>> res = new ArrayList<>(); res.add(new ArrayList<>()); for (int num : nums) { int size = res.size(); for (int i = 0; i < size; i++) { List<Integer> list = res.get(i); ArrayList<Integer> tmp = new ArrayList<>(); for (Integer integer : list) { tmp.add(integer); } tmp.add(num); res.add(tmp); } } return res; } }
优化方向:
上面的代码写法时间复杂度是O(n3)…因为我不知道原来ArrayList的构造函数支持直接将另一个ArrayList丢进去
优化一下代码,时间复杂度降到O(n2)
public List<List<Integer>> subsets(int[] nums) { if (nums.length == 0) { return new ArrayList<>(); } List<List<Integer>> res = new ArrayList<>(); res.add(new ArrayList<>()); for (int num : nums) { int size = res.size(); for (int i = 0; i < size; i++) { List<Integer> list = new ArrayList<>(res.get(i)); 这里不用取出来一个一个遍历来创建一个新List了 list.add(num); 直接使用Arraylist的构造函数,将需要复制的list丢进去就可以了 res.add(list); } } return res; }
性能:
这样时间复杂度就降下来了
2.位运算解决
解题思路:
- 因为假如数组长度有length,那么它的子集个数就有2length
- 可以想到用不同的位数来表示不同的子集
- 比如nums为【1,2,3】,那么下面为不同的子集
[0,0,0] = 【】
[0,0,1] = 【1】
[0,1,0] = 【2】
[0,1,1] = 【1,2】
[1,0,0] = 【3】
[1,0,1] = 【1,3】
[1,1,0] = 【2,3】
[1,1,1] = 【1,2,3】
代码:
public static List<List<Integer>> subsets(int[] nums) { //子集的长度是2的nums.length次方,这里通过移位计算 int length = 1 << nums.length; List<List<Integer>> res = new ArrayList<>(length); //遍历从0到length中间的所有数字,根据数字中1的位置来找子集 for (int i = 0; i < length; i++) { List<Integer> list = new ArrayList<>(); for (int j = 0; j < nums.length; j++) { //如果数字i的某一个位置是1,就把数组中对 //应的数字添加到集合 if (((i >> j) & 1) == 1) list.add(nums[j]); } res.add(list); } return res; }
这篇关于面试题 08.04. 幂集的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求