Should not this algorithm to be O(n2)???? But it did run quite slow.


  • 0
    S

    I thought the following algorithm is O(n2). However it behaves like O(n4). I don't know why.

    The idea of the following method is:
    1 Change n to n*n pairs, use the value of num[i]+num[j] as the key, and the vector<pair<int, int>> stores the indices.
    2 Use sum2 algorithm which will be O(n) and O(n2) acturally.

    I have used a counter to check how many calculations does it need. And the counter indicates the total calculation is O(n2). I don't know why. Please help.

    class Solution {
    public:
        vector<vector<int> > fourSum(vector<int> &num, int target) {
            vector<vector<int> > ret;
            sort(num.begin(), num.end());
            
            unordered_map<int, vector<pair<int, int>>> sink;
            for (int i=0; i<num.size(); i++) {
                for (int j=i+1; j<num.size(); j++) {
                    int key = num[i]+num[j];
                    if (sink.count(key)==0)
                        sink[key] = { make_pair(i, j) };
                    else {
                        sink[key].push_back(make_pair(i, j));
                    }
                }
            }
            
            for (unordered_map<int, vector<pair<int, int>>>::iterator iter = sink.begin() ; iter != sink.end(); ++iter) {
                int newTarget = target - iter->first;
                if (sink.find(newTarget)==sink.end()) {
                    continue;
                }
                
                vector<pair<int, int>> ary = sink[newTarget];
                vector<pair<int, int>> cur = iter->second;
    
                for (int i=int(ary.size()-1); i>=0; i--) {
                    if (i==ary.size()-1 || num[ary[i].first]!=num[ary[i+1].first]) {
                        for (int j=0; j<iter->second.size(); j++) {
                            if (cur[j].second < ary[i].first && (j==0 || num[cur[j].first]!=num[cur[j-1].first])) {
                                ret.push_back({num[cur[j].first], num[cur[j].second], num[ary[i].first], num[ary[i].second]});
                            }
                        }
                    }
                }
            }
            return ret;
        }
    };

  • 0
    H

    Actually, it is O(n2). But if the dataset is not large enough, there is no difference between O(n2) and O(n3)


Log in to reply
 

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