站点图标 AI技术聚合

算法leetcode｜90. 子集 II（rust重拳出击）

乘风

文章目录

  • 90. 子集 II：
    • 样例 1：
    • 样例 2：
    • 提示：
  • 分析：
  • 题解：
    • rust：
    • go：
    • c++：
    • python：
    • java：

90. 子集 II：

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

样例 1：

输入：
	
	nums = [1,2,2]
	
输出：
	
	[[],[1],[1,2],[1,2,2],[2],[2,2]]

样例 2：

输入：
	
	nums = [0]
	
输出：
	
	[[],[0]]

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

分析：

  • 面对这道算法题目，二当家的再次陷入了沉思。
  • 穷举数组的所有子集，每个数组元素都有被选择和不被选择两种情况，所以总的子集数量应该是 2n 个。
  • 数组中有重复元素，所以简单的按照选择不选择两种情况处理所有数组元素就会导致出现重复的子集，而题目是要求结果中不能包含重复子集的。
  • 简单的构建子集，然后判断子集是否已经在结果集中，当然是可行的，但是效率低下。
  • 先排序就可以用另一种方式去重，排序后相同的重复数组元素都会挨在一起，我们让选择某个数组元素值，变成计数，因为选其中任意一个都是相同的，同样选任意两个也是相同的，同理，相同元素选择任意多个，都与顺序位置无关，只与选择的个数有关。我们假定要求按照排序顺序选择，前面的选择了，后面的才有可能选择，这样就可以保证选择的数量不会重复，如果选择第二个，那么第一个一定也选择了，这也是选择两个的唯一方式，如果某个元素有三个，选择第三个时，必须前两个也都是选择的，不能选择任意位置的相同元素，这样就可以保证个数决定位置，从而达到去重的效果。
  • 另外，排序不是目的，只是为了方便去重，这种情况，二当家的认为用计数排序是最好的，尤其是元素种类提前知道，并且较少的情况。

题解：

rust：

impl Solution {
    pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut ans = Vec::new();

        let mut nums = nums;

        // 排序
        nums.sort();

        let n = nums.len();

        // 每一个数都有选择和不选2种情况，穷举所有可能
        (0..(1 << n)).for_each(|mask| {
            let mut row = Vec::new();
            let mut flag = true;
            for i in 0..n {
                if (mask & (1 << i)) != 0 {
                    if i > 0 && nums[i] == nums[i - 1] && (mask & (1 << (i - 1))) == 0 {
                        // 配合排序去重（上一个数没选，这一个也不选，否则就和之前选择上一个的分支发生重复）
                        flag = false;
                        break;
                    }
                    row.push(nums[i]);
                }
            }
            if flag {
                ans.push(row);
            }
        });

        return ans;
    }
}

go：

func subsetsWithDup(nums []int) [][]int {
    var ans [][]int
	// 排序
	sort.Ints(nums)
	n := len(nums)

outer:
	// 每一个数都有选择和不选2种情况，穷举所有可能
	for mask := 0; mask < (1 << n); mask++ {
		var row []int
		for i, v := range nums {
			if mask&(1<<i) > 0 {
				// 配合排序去重（上一个数没选，这一个也不选，否则就和之前选择上一个的分支发生重复）
				if i > 0 && v == nums[i-1] && (mask&(1<<(i-1))) == 0 {
					continue outer
				}
				row = append(row, v)
			}
		}
		ans = append(ans, row)
	}

	return ans
}

c++：

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ans;
        // 排序
        sort(nums.begin(), nums.end());
        int n = nums.size();

        // 每一个数都有选择和不选2种情况，穷举所有可能
        for (int mask = 0; mask < (1 << n); ++mask) {
            vector<int> row;
            bool flag = true;
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    // 配合排序去重（上一个数没选，这一个也不选，否则就和之前选择上一个的分支发生重复）
                    if (i > 0 && nums[i] == nums[i - 1] && (mask & (1 << (i - 1))) == 0) {
                        flag = false;
                        break;
                    }
                    row.emplace_back(nums[i]);
                }
            }
            if (flag) {
                ans.emplace_back(row);
            }
        }

        return ans;
    }
};

python：

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        ans = []
        # 排序
        nums.sort()
        n = len(nums)
        # 每一个数都有选择和不选2种情况，穷举所有可能
        for mask in range(1 << n):
            flag = True
            row = []
            for i in range(n):
                if mask & (1 << i):
                    # 配合排序去重（上一个数没选，这一个也不选，否则就和之前选择上一个的分支发生重复）
                    if i > 0 and nums[i] == nums[i - 1] and (mask & (1 << (i - 1))) == 0:
                        flag = False
                        break
                    row.append(nums[i])
            if flag:
                ans.append(row)
        return ans

java：

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        final List<List<Integer>> ans = new ArrayList<>();
        // 排序
        Arrays.sort(nums);
        final int n = nums.length;
        // 每一个数都有选择和不选2种情况，穷举所有可能
        for (int mask = 0; mask < (1 << n); ++mask) {
            final List<Integer> row  = new ArrayList<>();
            boolean             flag = true;
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    // 配合排序去重（上一个数没选，这一个也不选，否则就和之前选择上一个的分支发生重复）
                    if (i > 0 && nums[i] == nums[i - 1] && (mask & (1 << (i - 1))) == 0) {
                        flag = false;
                        break;
                    }
                    row.add(nums[i]);
                }
            }
            if (flag) {
                ans.add(row);
            }
        }
        return ans;
    }
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

文章出处登录后可见！

已经登录？立即刷新
退出移动版