最大整除子集-LintCode

104 阅读 0 评论 69 点赞

我是靠谱客的博主悲凉蜻蜓，这篇文章主要介绍最大整除子集-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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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