largest-divisible-subset-白红宇

largest-divisible-subset

阅读量：7072 次

发布时间：2019-06-28

本文共 2155 字，大约阅读时间需要 7 分钟。

用了两种方法：

class Solution {    // size of vector -> set of last item of vector    map

> size_mp; // last item of vector -> whole vector map

> result_mp; public: // if new item can divide last item, it can divide all items in vector, // so that no need to check previous item vector

largestDivisibleSubset(vector

& nums) { if (nums.size() < 1) { return nums; } sort(nums.begin(), nums.end()); for (vector

::iterator itr = nums.begin(); itr != nums.end(); ++itr) { // only need prev item to get whole items from result_mp int prev = -1; // iterator from longer vector to shorter for (map

>::reverse_iterator ritr = size_mp.rbegin(); ritr != size_mp.rend(); ++ritr) { for (set

::iterator sitr = ritr->second.begin(); sitr != ritr->second.end(); ++sitr) { // if last item of long vector can divide new number, // no need to check other vector or previous item if (*itr % *sitr == 0) { prev = *sitr; break; } } if (prev != -1) { break; } } vector

tmp_vec; if (prev != -1) { tmp_vec = result_mp[prev]; } tmp_vec.push_back(*itr); result_mp[*itr] = tmp_vec; int newsize = tmp_vec.size(); if (size_mp.find(newsize) == size_mp.end()) { set

tmp_set; tmp_set.insert(*itr); size_mp[newsize] = tmp_set; } else { size_mp[newsize].insert(*itr); } } set

::iterator sitr_new = size_mp.rbegin()->second.begin(); return result_mp[*sitr_new]; } };

31 / 31 test cases passed.	Status: Accepted
Runtime: 261 ms

开始用的下面这种方法，超时了：

class Solution {    vector
     
       nums;    int nlen;    vector
      
        result;        void func(vector
       
        & iv, int index) {        int vlen = iv.size();        int divisor = 1;        if (vlen > 0) {            divisor = iv[vlen-1];        }                for (int k=index; k
        
          result.size()) {            result = iv;        }    }    public:    vector
         
           largestDivisibleSubset(vector
          
           & arg) { nums = arg; sort(nums.begin(), nums.end()); nlen = nums.size(); if (nlen <= 1) { return nums; } vector
           
             tmp; func(tmp, 0); return result; } };

转载于:https://www.cnblogs.com/charlesblc/p/5623319.html

Accepted