0368. Largest Divisible Subset
==============================
题目信息
--------
:题号: 0368
:难度: Medium
:主题: 正整数集合、两两整除、最大子集、答案不唯一
:原题: `LeetCode 0368 `_
:重点: 输入元素互不相同、子集中任意两数都必须可整除、返回元素数量最多的任意一个子集
题目重述
--------
给定一个由互不相同正整数组成的数组 ``nums``,寻找元素数量最多的子集 ``answer``,使其中任意两个不同元素 ``a`` 和 ``b`` 都满足 ``a % b == 0`` 或 ``b % a == 0``。
数组长度位于 ``[1, 1000]``,元素位于 ``[1, 2 * 10^9]``。若存在多个同样大的合法子集,可以返回其中任意一个;返回元素的排列顺序不作要求。题目要求的是从输入元素中选择子集,不能重复使用某个位置。
自建示例
--------
存在唯一更长的整除链:
.. code-block:: text
输入:nums = [3,5,10,20,21]
输出:[5,10,20]
解释:5 整除 10 和 20,10 也整除 20,因此三者两两满足条件;其他元素无法加入后仍保持两两可整除。
多个最大答案均可接受:
.. code-block:: text
输入:nums = [1,2,3]
输出:[1,2]
解释:[1,3] 也是大小为 2 的最大合法子集,题目允许返回任意一个。
排序后,合法子集就是一条整除链
--------------------------------
将数组升序排序。若一个已选子集按升序排列,并且每个新元素都能被当前链的最后一个元素整除,那么链中任意更早元素也能整除新元素,因而“最后一个整除前一个”的条件足以保证任意两数可比较。
令 ``dp[i]`` 表示以排序后第 ``i`` 个数结尾的最长整除链长度。若 ``nums[i] % nums[j] == 0``,就可以把 ``i`` 接在以 ``j`` 结尾的链后;同时记录 ``parent[i]``,最后从最长结尾反向恢复一个合法子集。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector largestDivisibleSubset(
std::vector& nums) {
std::sort(nums.begin(), nums.end());
int n = static_cast(nums.size());
std::vector dp(n, 1);
std::vector parent(n, -1);
int bestIndex = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] % nums[j] == 0
&& dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
parent[i] = j;
}
}
if (dp[i] > dp[bestIndex]) bestIndex = i;
}
std::vector result;
for (int i = bestIndex; i != -1; i = parent[i]) {
result.push_back(nums[i]);
}
std::reverse(result.begin(), result.end());
return result;
}
};
代码分析
--------
排序把可能的除数放在被除数之前,状态转移只需检查前面的元素;链式整除保证恢复结果中的任意两数都满足题目条件。每个有序下标对检查一次,时间复杂度为 ``O(n^2)``,额外空间为 ``O(n)``;排序会改变输入数组顺序,但题目只要求返回子集。