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^9
  • nums 中的所有整数 互不相同

解题思路

这道题的核心思想是利用动态规划和排序的性质。

首先观察题目要求：子集中任意两个数都要满足整除关系。这意味着如果我们将子集按升序排列，那么相邻的数字也必须满足整除关系，即 a[i] % a[i-1] == 0。

算法步骤：

  1. 排序：将数组排序，这样可以保证如果 a < b < c 且 b % a == 0, c % b == 0，那么 c % a == 0 也成立（整除的传递性）。

  2. 动态规划：

    • dp[i] 表示以 nums[i] 结尾的最长整除子集的长度
    • parent[i] 记录前驱元素的索引，用于构造最终答案

  3. 状态转移：对于每个位置 i，检查所有之前的位置 j，如果 nums[i] % nums[j] == 0，则可以将 nums[i] 加入到以 nums[j] 结尾的子集中。

  4. 路径重建：通过 parent 数组反向构造最长的整除子集。

时间复杂度主要来自双重循环，空间复杂度用于存储 dp 和 parent 数组。

代码实现

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        vector<int> dp(n, 1);
        vector<int> parent(n, -1);
        
        int maxLen = 1;
        int maxIndex = 0;
        
        for (int i = 1; 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] > maxLen) {
                maxLen = dp[i];
                maxIndex = i;
            }
        }
        
        vector<int> result;
        int curr = maxIndex;
        while (curr != -1) {
            result.push_back(nums[curr]);
            curr = parent[curr];
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()
        
        dp = [1] * n
        parent = [-1] * n
        
        max_len = 1
        max_index = 0
        
        for i in range(1, n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    parent[i] = j
            
            if dp[i] > max_len:
                max_len = dp[i]
                max_index = i
        
        result = []
        curr = max_index
        while curr != -1:
            result.append(nums[curr])
            curr = parent[curr]
        
        result.reverse()
        return result

public class Solution {
    public IList<int> LargestDivisibleSubset(int[] nums) {
        int n = nums.Length;
        Array.Sort(nums);
        
        int[] dp = new int[n];
        int[] parent = new int[n];
        Array.Fill(dp, 1);
        Array.Fill(parent, -1);
        
        int maxLen = 1;
        int maxIndex = 0;
        
        for (int i = 1; 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] > maxLen) {
                maxLen = dp[i];
                maxIndex = i;
            }
        }
        
        List<int> result = new List<int>();
        int curr = maxIndex;
        while (curr != -1) {
            result.Add(nums[curr]);
            curr = parent[curr];
        }
        
        result.Reverse();
        return result;
    }
}

var largestDivisibleSubset = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const dp = new Array(n).fill(1);
    const parent = new Array(n).fill(-1);
    
    let maxLen = 1;
    let maxIndex = 0;
    
    for (let i = 1; i < n; i++) {
        for (let 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] > maxLen) {
            maxLen = dp[i];
            maxIndex = i;
        }
    }
    
    const result = [];
    let current = maxIndex;
    while (current !== -1) {
        result.unshift(nums[current]);
        current = parent[current];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要双重循环遍历数组进行状态转移
空间复杂度O(n)需要 dp 和 parent 数组存储状态信息