幂集。编写一种方法,返回某集合的所有子集。集合中不包含重复的元素。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
代码思路:
代码:
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; }
性能:
这样时间复杂度就降下来了
解题思路:
[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; }