Is it possible to solve this problem in REAL O(n) complexity? Without HashMap.


  • 1
    P

    Has any one an idea how to solve this problem without using HashMap? I don't think that when using map.find() or map.contains() inside for-next solution complexity still remains O(n).

    Please, correct me if i'm wrong.


  • 2
    B

    To answer the second part of your question, if your solution inserts and erases each element from the hashMap exactly once, it is O(n).


  • 0
    W

    i use radix sort to do O(n). although it takes more memory than solution using hashmap, it also use O(n) memory.

    class Solution {
    public:
        int longestConsecutive(vector<int> &num) {
            vector<int> radix[11][19];
            for (int it = 0; it < num.size(); ++it) {
                radix[0][num[it]%10+9].push_back(num[it]);
            }
            int pow10 = 1;
            for (int i = 1; i < 11; ++i) {
                pow10 *= 10;
                for (int j = 0; j < 19; ++j) {
                    for (vector<int>::iterator it = radix[i-1][j].begin(); it != radix[i-1][j].end(); ++it) {
                        radix[i][((*it)/pow10)%10+9].push_back(*it);
                    }
                }
            }
            vector<int> ans;
            for (int j = 0; j < 19; ++j) {
                for (vector<int>::iterator it = radix[10][j].begin(); it != radix[10][j].end(); ++it) {
                    ans.push_back(*it);
                }
            }
            int cons = 0, longest = 0;;
            int prev = 0;
            for (int it = 0; it < ans.size(); ++it) {
                printf("%d ", ans[it]);
                if (cons) {
                    if (ans[it-1]+1 == ans[it]) {
                        cons++;
                        prev = ans[it];
                    }
                    else if (ans[it-1] != ans[it]) {
                        cons = 0;
                    }
                }
                if (cons == 0) {
                    cons = 1;
                    prev = ans[it];
                }
                longest = max(longest, cons);
            }
            longest = max(longest, cons);
            return longest;
        }
    };

Log in to reply
 

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