最大整除子集

难度: Medium

给你一个由 无重复 正整数组成的集合 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 <= 1000
1 <= nums[i] <= 2 * 10⁹
nums 中的所有整数 互不相同

Submission

运行时间: 171 ms

内存: 0.0 MB

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        topo, route = defaultdict(list), {}
        for n in sorted(nums):
            i = len(topo)
            while (i := i - 1) >= 0:
                for m in topo[i]:
                    if n % m == 0:
                        topo[i + 1].append(n)
                        route[n], i = m, 0
                        break
            if n not in route:
                topo[0].append(n)
                route[n] = None

        ret, n = [], topo[len(topo) - 1][0]
        while n:
            ret.append(n)
            n = route[n]
        return ret

Explain

该题解采用了拓扑排序的思想。首先将数组按照升序排序，然后遍历排序后的数组，对于每个元素，找到满足整除条件的前驱元素，并将当前元素添加到相应的拓扑层级中。同时，使用一个字典 route 记录每个元素的前驱元素。最后，从拓扑层级的最后一层开始，通过 route 字典回溯得到最大整除子集。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        # 使用字典 topo 存储拓扑层级，字典 route 记录每个元素的前驱元素
        topo, route = defaultdict(list), {}
        # 将数组按照升序排序
        for n in sorted(nums):
            i = len(topo)
            while (i := i - 1) >= 0:
                # 遍历已处理的元素，找到满足整除条件的前驱元素
                for m in topo[i]:
                    if n % m == 0:
                        topo[i + 1].append(n)
                        route[n], i = m, 0
                        break
            # 如果当前元素没有找到前驱元素，将其添加到拓扑层级的第 0 层
            if n not in route:
                topo[0].append(n)
                route[n] = None
        
        # 从拓扑层级的最后一层开始回溯，得到最大整除子集
        ret, n = [], topo[len(topo) - 1][0]
        while n:
            ret.append(n)
            n = route[n]
        return ret

Explore

对数组进行排序的目的是为了方便找到元素的前驱元素，保证子集中的每个元素都可以被后面的元素整除。因为如果一个较小的数不能整除当前的数，那么比它大的数也不可能整除当前的数。排序使得算法可以顺序检查每个元素，并尝试将其添加到已存在的符合条件的子集中，这样可以有效地构建出满足条件的最大子集。

题解中所说的拓扑排序思想主要体现在通过层级结构组织数据，每个元素根据其前驱元素的条件（整除关系）被分配到不同的层级。这里的“层级”概念类似于拓扑排序中处理依赖关系的层次。拓扑排序通常用于解决具有依赖关系的任务安排问题，如项目中的任务执行顺序，编译依赖等，确保每个任务只在其依赖的任务完成后才开始。

`topo`字典用于存储不同层级的元素，其中每个层级包含能被该层级之前所有元素整除的所有元素。`route`字典记录每个元素的直接前驱元素，这是为了在构建完所有层级后能够回溯找到形成最大整除子集的路径。这两个字典对算法至关重要，`topo`确保了元素可以按照依赖关系（整除条件）正确分层，而`route`使得最终能够从结果集中恢复出最大的整除子集。

将没有找到满足整除条件的前驱元素的当前元素n添加到第0层，意味着它不能被之前的任何元素整除，因此它本身可以作为一个新的子集的开始。这样做的优势在于，它保证了算法可以捕捉到所有可能的开始点，从而不遗漏任何潜在的最大整除子集。这也有助于在没有任何其他元素可以整除某个元素时，仍然能够将其考虑进最终的解集中。