368. 最大整除子集¶

难度：中等

题目¶

给你一个由 无重复 正整数组成的集合 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^9
nums 中的所有整数 互不相同

Reference

题解¶

整数之间的整除关系满足自反性、反对称性和传递性，使用$a|b$表示$a$可以被$b$整除，则：

自反性：$a|a = T$
反对称性：$a|b \overline \lor b|a = T$
传递性：$a|b \land b|c\Rightarrow a|c$

因此，整除关系是正整数集$N_+$上的相容关系与偏序关系。

设正整数集合为$S$，以下基于偏序关系$R$与偏序集$S$定义链的概念：

若$a\in S, b\in S$，且$a|b \lor b|a$，则$a, b$是可比的；
若集合$B\subseteq S$，且对于$B$中任意一对元素$x, y$都是可比的，则称$B$为偏序集$S$上的链。
偏序集$S$中包含元素最多的链称为最长链。

由此可见，所求的最大整除子集即为$S$上的最长链。

偏序集可以使用哈斯图进行表示，如集合$\{2,3,4,6,8\}$上的偏序关系可以表示为如下所示：

$hass_graph$

哈斯图是有向无环图，但不一定连通。链在哈斯图中表现为一段路径，最长链即为哈斯图中的最长路径，即各分量的最长直径，如图中加粗线条所示。

因此，可以使用图解决本题，第一步构造偏序集的哈斯图，流程如下：

对集合排序，对于集合中的每个元素，在图中创建一个元素与之对应；
从后向前遍历集合，对于每个节点$a_i$：
1. 从第$i + 1$个元素开始，向后遍历集合，对于每个节点$a_j$，若$a_j|a_i$，并且不存在更小的节点与$a_i$相连，则将节点$i$与节点$j$相连接。

为了快速求出图的直径，可在节点中存储两个值，即：

当前节点距离末端节点（出度为$0$的节点）的最大距离
当前节点距离末端节点最大距离所对应的出边

由于整除关系蕴含小于等于关系，因此在构造哈斯图时，可以同时构造这两个值。

第二步即可找出最长直径。遍历所有入度为$0$的节点，找出并记下距离末端节点最远的节点。再根据节点中存储的出边信息即可完整构造所需的最大整除子集。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define MAX(x, y) ((x) > (y) ? (x) : (y))
struct Edge;
struct Vertex;
struct Edge
{
    struct Vertex *dest;
    struct Edge *next;
};
struct Vertex
{
    int val;
    int status;
    struct Edge *edges;
    int height;
    struct Edge *maxHeight;
};
struct Edge *getEdge(struct Vertex *dest, struct Edge *next)
{
    struct Edge *cur = next;
    while (cur)
    {
        if (dest->val % cur->dest->val == 0)
            return next;
        cur = cur->next;
    }
    struct Edge *ret = (struct Edge *)malloc(sizeof(struct Edge));
    ret->dest = dest;
    ret->next = next;
    return ret;
}
int cmp(const void *a, const void *b)
{
    return *((int *)a) - *((int *)b);
}
void dfs(struct Vertex *graph)
{
    if (graph == NULL)
        return;
    graph->status = true;
    struct Edge *edge = graph->edges;
    while (edge)
    {
        dfs(edge->dest);
        edge = edge->next;
    }
}
int* largestDivisibleSubset(int* nums, int numsSize, int* returnSize){
    struct Vertex *nodes = (struct Vertex *)malloc(sizeof(struct Vertex) * numsSize), *maxVertex = NULL;
    int i = 0, j = 0, max = -1, *ret = NULL;
    qsort(nums, numsSize, sizeof(int), cmp);
    for (i = 0; i < numsSize; i++)
    {
        nodes[i].val = nums[i];
        nodes[i].status = 0;
        nodes[i].edges = NULL;
        nodes[i].height = 0;
        nodes[i].maxHeight = NULL;
    }
    for (i = numsSize - 1; i >= 0; i--)
    {
        for (j = i + 1; j < numsSize; j++)
        {
            if (nodes[j].val % nodes[i].val)
                continue;
            nodes[i].edges = getEdge(nodes + j, nodes[i].edges);
            if (nodes[i].height < nodes[j].height + 1)
            {
                nodes[i].height = nodes[j].height + 1;
                nodes[i].maxHeight = nodes[i].edges;
            }
        }
    }
    for (i = 0; i < numsSize; i++)
    {
        if (nodes[i].status)
            continue;
        if (nodes[i].height > max)
        {
            max = nodes[i].height;
            maxVertex = nodes + i;
        }
        dfs(nodes + i);
    }
    *returnSize = max + 1;
    ret = (int *)malloc(sizeof(int) * (max + 1));
    for (i = 0; i <= max; i++)
    {
        ret[i] = maxVertex->val;
        if (maxVertex->maxHeight == NULL)
            break;
        maxVertex = maxVertex->maxHeight->dest;
    }
    return ret;
}

368. 最大整除子集¶

题目¶

题解¶

评论