最大整除子集-LintCode

给一个由 无重复的正整数 组成的集合，找出满足任意两个元素 (Si, Sj) 都有 Si % Sj = 0 或 Sj % Si = 0 成立的最大子集

注意事项：
如果有多种解集，返回其中任意一个。

样例：
给一个数组 [1,2,3]，返回 [1,2] 或 [1,3]
给一个数组 [1,2,4,8]，返回 [1,2,4,8]

#ifndef C603_H
#define C603_H
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
class Solution {
public:
    /*
    * @param nums: a set of distinct positive integers
    * @return: the largest subset
    */
    vector<int> largestDivisibleSubset(vector<int> &nums) {
        // write your code here
        vector<int> res;
        if (nums.empty())
            return res;
        int len = nums.size();
        sort(nums.begin(), nums.end());
        map<int, vector<int>> m;//存放元素与其对应的整除子集
        vector<int> num;
        for (int i = 0; i < len; ++i)
        {
            num.clear();
            for (int j = i - 1; j >= 0; --j)//遍历i之前的元素
            {
                if (nums[i] % nums[j] == 0 && m[nums[j]].size()>num.size())//找到nums[i]可以整除且最长的整除数组
                {
                    num = m[nums[j]];
                }               
            }
            num.push_back(nums[i]);//nums[i]加到此数组后面,当i==1或者前面没有可以整除的数字，就直接加上自身
            m[nums[i]] = num;//更新map
        }
        for (auto c : m)    //获得最长的整除子集
        {
            if (c.second.size() > res.size())
                res = c.second;
        }
        return res;
    }
};
#endif

最后

以上就是悲凉蜻蜓为你收集整理的最大整除子集-LintCode的全部内容，希望文章能够帮你解决最大整除子集-LintCode所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。