当前位置：首页 > article >正文

20240209-最大可整分子集

article 2024/11/15 5:25:38

题目要求

给定一组不同的正整数 nums，返回最大的子集 answer，使得该子集中的每一对元素（answer[i], answer[j]）都满足：

answer[i] % answer[j] == 0，或
answer[j] % answer[i] == 0
如果有多个解决方案，则返回其中任意一个。

Example 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

Input: nums = [1,2,4,8]
Output: [1,2,4,8]

思路

再次推荐一下labuladong，东哥的题解和思路写的都很好。

首先通过观察发现这个题目是一个穷举问题，但是由于数据量巨大，所以阶乘级别的时间复杂度是不行的。

再思考一下，在数组中寻找一个特定要求的子序列，那么如果我们把数组进行排列，这个题目就变成了寻找“最长上升子序列”类似的题目，因为我们要求每两个数之间具备整除关系，这就意味着其中一个一定大于等于另一个。

排序很重要，假设一个符合题目要求的子集 [1,2,4]，那么由于我排了序，如果想扩充这个集合，接下来我只要到一个能够整除 4 的数就行了，比如 8。我不用考虑前面的数字了，因为只要能整除最大的 4 就一定能整除别的。

这样一来，题目就变成了：寻找一个最长递增子序列，且要求每个元素都能够整除前面那个元素。

那么我们只需要定义一个dp数组，dp[i]代表了以nums[i]结尾的最长上升可整除子序列的个数。要求新加入的元素能够整除前一个元素，所以这里在遍历i的同时，可能还需要遍历之前所有的数来检查是否能够整除：dp[i] = max(dp[i], dp[j]+1) {if nums[i] % nums[j] == 0}

现在我们还有一个点需要注意，因为我们需要返回的是最长的子集，因此我们不能只存储最长的子集。我们需要在判断dp[i]和dp[j]的大小时，动态的存储i对应的前一位的位置j。

代码

注意在回溯获得最长子集的过程中采用的for循环。

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> dp(n, 1), parent(n, -1);
        vector<int> result;
        int maxIndex = 0;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                    if (dp[i] > dp[maxIndex]) {
                        maxIndex = i;
                    }
                }
            }
        }
        for (int i = maxIndex; i != -1; i = parent[i]) {
            result.push_back(nums[i]);
        }
        return result;
    }
};