Solution using 2 maps in C++ with comments, 256 ms


  • 0
    B

    Optimization:

    1. use size_map to record vector size, iterate from longer vector to shorter vector
    2. only check last item of each vector, no need to check preview ones
    3. use result_map to record vector result, to reduce vector copy.
    
    
    class Solution {
        // size of vector -> set of last item of vector
        map<int, set<int>> size_mp;
        // last item of vector -> whole vector
        map<int, vector<int>> result_mp;
        
    public:
        // if new item can be divided by last item, so be all items in vector,
        // so that no need to check previous item
        vector<int> largestDivisibleSubset(vector<int>& nums) {
            if (nums.size() < 1) {
                return nums;
            }
            
            sort(nums.begin(), nums.end());
            
            for (vector<int>::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<int, set<int>>::reverse_iterator ritr = size_mp.rbegin();
                     ritr != size_mp.rend(); ++ritr) {
                
                    for (set<int>::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;
                    }
                }
                
                // add current result to result_mp
                vector<int> 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();
                
                // add current result to size_mp
                if (size_mp.find(newsize) == size_mp.end()) {
                    set<int> tmp_set;
                    tmp_set.insert(*itr);
                    size_mp[newsize] = tmp_set;
                }
                else {
                    size_mp[newsize].insert(*itr);
                }
                
            }
            
            set<int>::iterator sitr_new = size_mp.rbegin()->second.begin();
            return result_mp[*sitr_new];
            
        }
        
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.