0368. Largest Divisible Subset

题目信息

题号:

0368

难度:

Medium

主题:

正整数集合、两两整除、最大子集、答案不唯一

原题:

LeetCode 0368

重点:

输入元素互不相同、子集中任意两数都必须可整除、返回元素数量最多的任意一个子集

题目重述

给定一个由互不相同正整数组成的数组 nums,寻找元素数量最多的子集 answer,使其中任意两个不同元素 a 和 b 都满足 a % b == 0 或 b % a == 0。

数组长度位于 [1, 1000],元素位于 [1, 2 * 10^9]。若存在多个同样大的合法子集,可以返回其中任意一个;返回元素的排列顺序不作要求。题目要求的是从输入元素中选择子集,不能重复使用某个位置。

自建示例

存在唯一更长的整除链:

输入:nums = [3,5,10,20,21]
输出:[5,10,20]
解释:5 整除 10 和 20,10 也整除 20,因此三者两两满足条件;其他元素无法加入后仍保持两两可整除。

多个最大答案均可接受:

输入:nums = [1,2,3]
输出:[1,2]
解释:[1,3] 也是大小为 2 的最大合法子集,题目允许返回任意一个。

排序后,合法子集就是一条整除链

将数组升序排序。若一个已选子集按升序排列,并且每个新元素都能被当前链的最后一个元素整除,那么链中任意更早元素也能整除新元素,因而“最后一个整除前一个”的条件足以保证任意两数可比较。

令 dp[i] 表示以排序后第 i 个数结尾的最长整除链长度。若 nums[i] % nums[j] == 0,就可以把 i 接在以 j 结尾的链后;同时记录 parent[i],最后从最长结尾反向恢复一个合法子集。

C++ 实现

class Solution {
public:
    std::vector<int> largestDivisibleSubset(
        std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        int n = static_cast<int>(nums.size());
        std::vector<int> dp(n, 1);
        std::vector<int> 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<int> 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);排序会改变输入数组顺序,但题目只要求返回子集。