最大整除子集
难度:
标签:
题目描述
给你一个由 无重复 正整数组成的集合
nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
answer[i] % answer[j] == 0，或answer[j] % answer[i] == 0
如果存在多个有效解子集，返回其中任何一个均可。
示例 1：
输入：nums = [1,2,3] 输出：[1,2] 解释：[1,3] 也会被视为正确答案。
示例 2：
输入：nums = [1,2,4,8] 输出：[1,2,4,8]
提示：
1 <= nums.length <= 10001 <= nums[i] <= 2 * 109nums中的所有整数 互不相同
代码结果
运行时间: 171 ms, 内存: 0.0 MB
// 使用Java Stream的题解代码和注释
// 题目思路：
// 1. 对数组nums进行排序
// 2. 使用动态规划的方式记录以每个元素为结尾的最大整除子集的长度和前驱元素
// 3. 最终从最大长度的子集开始回溯找到完整的最大整除子集
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums); // 对nums进行排序
int[] dp = new int[nums.length]; // dp[i]表示以nums[i]为结尾的最大整除子集的长度
int[] prev = new int[nums.length]; // prev[i]表示在nums[i]前一个元素的索引
int maxSize = 0; // 最大子集的大小
int maxIndex = -1; // 最大子集的最后一个元素的索引
// 初始化
Arrays.fill(dp, 1); // 每个元素自身可以构成一个子集
Arrays.fill(prev, -1); // 初始化前驱数组
// 动态规划计算每个元素的最大子集大小
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
// 更新最大子集的大小和最后一个元素的索引
if (dp[i] > maxSize) {
maxSize = dp[i];
maxIndex = i;
}
}
// 回溯最大整除子集
List<Integer> result = new ArrayList<>();
for (int i = maxIndex; i >= 0; i = prev[i]) {
result.add(nums[i]);
if (prev[i] == -1) break;
}
return result.stream().collect(Collectors.toList());
}
}解释
方法:
该题解采用了拓扑排序的思想。首先将数组按照升序排序，然后遍历排序后的数组，对于每个元素，找到满足整除条件的前驱元素，并将当前元素添加到相应的拓扑层级中。同时，使用一个字典 route 记录每个元素的前驱元素。最后，从拓扑层级的最后一层开始，通过 route 字典回溯得到最大整除子集。
时间复杂度:
O(n^2)
空间复杂度:
O(n^2)
代码细节讲解
🦆
为什么在解决最大整除子集问题时，选择先对数组进行排序？排序的目的是什么？
▷🦆
在题解中提到的拓扑排序思想，具体是如何应用在这个问题上的？拓扑排序通常用于解决什么类型的问题？
▷🦆
题解中使用了两个字典`topo`和`route`，能否详细解释这两个字典各自的作用及其在算法中的重要性？
▷🦆
在构建拓扑层级时，如果当前元素n没有找到任何满足整除条件的前驱元素，为何选择将其添加到拓扑层级的第0层？这样做有什么特别的意义或优势？
▷