网站安全维护,网站备案号信息查询,wordpress不能放大图片,微信推广平台哪个好题目
90. 子集 II
中等
相关标签
位运算 数组 回溯
给你一个整数数组 nums #xff0c;其中可能包含重复元素#xff0c;请你返回该数组所有可能的子集#xff08;幂集#xff09;。
解集 不能 包含重复的子集。返回的解集中#xff0c;子集可以按 任意顺序 排列…题目
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
思路和解题方法 首先定义了私有成员变量result和path分别用于存储最终结果和当前路径。result是一个二维向量每个元素是一个一维向量表示一个子集。path是一个一维向量表示当前路径。接下来是私有函数backtracking它是实现回溯算法的核心部分。回溯算法是一种通过穷举所有可能的搜索方式然后根据条件进行剪枝的算法。在这里回溯算法用于生成给定数组的所有子集并避免生成重复的子集。在backtracking函数中首先将当前路径path加入到结果集result中即将当前路径作为一个子集加入结果集。接着使用循环从startIndex开始遍历数组nums的元素。对于每个元素nums[i]判断其是否与前一个元素相同且不是起始位置。如果是则跳过该元素以避免生成重复的子集。这个判断条件if (i startIndex nums[i] nums[i-1])起到了去重的作用。如果当前元素需要包含在子集中则将其加入到当前路径path中。然后递归调用backtracking函数以处理下一个元素。递归调用时将startIndex设置为i 1表示从当前元素的下一个元素开始进行处理。当递归调用完成后进行回溯操作。即将路径path中的当前元素移除尝试其他选择继续搜索其他子集。最后公共函数subsetsWithDup是对外的接口函数。它首先清空结果集result和路径path以便重新计算子集。然后对输入数组nums进行排序以便处理重复元素的情况。排序后调用backtracking函数从索引0开始进行回溯搜索。最终返回结果集result。 复杂度 时间复杂度: O(2^N * N) 该代码的时间复杂度为 O(2^N * N)其中 N 是数组 nums 的长度。 在回溯函数 backtracking 中我们遍历了所有可能的子集组合。每个元素都有两种状态选中和不选中因此总共有 2^N 种可能的子集。在每次添加到结果集中时需要复制一份当前路径 path并将其加入到结果集中这个操作的时间复杂度是 O(N)。 因此回溯函数的时间复杂度为 O(2^N * N)。 空间复杂度 O(N) 对于空间复杂度主要耗用的是递归调用栈的空间。在最坏情况下递归的深度可以达到 N所以空间复杂度是 O(N)。另外还需要额外的空间来存储结果集和当前路径因此额外的空间复杂度是 O(N)。 c 代码
class Solution {
private:vectorvectorint result; // 存储最终结果的二维向量vectorint path; // 存储当前路径的一维向量void backtracking(vectorint nums, int startIndex) {result.push_back(path); // 将当前路径加入结果集中for (int i startIndex; i nums.size(); i) {if (i startIndex nums[i] nums[i-1]) {continue; // 如果遇到重复的元素则跳过避免生成重复的子集}//重要 相邻两个去重path.push_back(nums[i]); // 将当前元素加入路径中backtracking(nums, i 1); // 递归调用处理下一个元素path.pop_back(); // 回溯将当前元素移出路径尝试其他选择}}public:vectorvectorint subsetsWithDup(vectorint nums) {result.clear(); // 清空结果集path.clear(); // 清空路径sort(nums.begin(), nums.end()); // 对数组进行排序以便处理重复元素backtracking(nums, 0); // 调用回溯函数从索引0开始搜索return result; // 返回最终的结果集}
};分析 if (i startIndex nums[i] nums[i-1]) {continue; // 如果遇到重复的元素则跳过避免生成重复的子集}//重要 相邻两个去重 代码是为了避免生成重复的子集而进行的判断和跳过操作。 首先根据题目要求我们需要找到给定数组中所有不重复的子集。如果数组中存在重复的元素并且我们在生成子集时不进行特殊处理就有可能生成重复的子集。 在这段代码中通过比较当前元素 nums[i] 和前一个元素 nums[i-1] 是否相等来判断是否遇到重复的元素。为了确保判断的准确性和避免数组越界还需要额外的条件 i startIndex 来保证当前元素 nums[i] 不是起始位置的元素。 如果发现相邻两个元素相等就说明当前元素 nums[i] 与前一个元素 nums[i-1] 是重复的。为了避免生成重复的子集我们直接使用 continue 关键字跳过当前循环不将当前元素 nums[i] 加入到当前路径 path 中。 这样当数组中有连续重复的元素时我们只会选择其中的一个从而避免了生成重复的子集。 需要注意的是在进行这一判断和跳过操作之前必须确保数组 nums 是已经按照非降序排序的这样才能保证重复的元素是相邻的。否则不相邻的重复元素也可能被认为是重复的导致错误结果。 综上所述这段代码通过比较当前元素与前一个元素是否相等来判断是否遇到重复的元素并通过 continue 关键字跳过重复元素以避免生成重复的子集。 觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
