It get wrong on OJ, but test right in my local PC, I have checked that no global or static value


  • 0
    R
    struct length
    {
    	int count;
    	bool left;
    	bool right;
    };
    class Solution {
    public:
    int longestConsecutive(vector<int> &num) {
            unordered_map<int,length> map;
    		length l;
    		l.count=1;l.left=false;l.right=false;
    		for(int i=0;i<num.size();i++)
    		{
    			if(map.find(num.at(i))==map.end())
    				map[num.at(i)]=l;
    		}
    		unordered_map<int,length>::iterator it;
    		for(it=map.begin();it!=map.end();it++)
    		{
    			if(it->second.left==false)
    			{
    				if(map.find(it->first-1)!=map.end() && map[it->first-1].right==false)
    				{
    					int sumlength=map[it->first].count+map[it->first-1].count;
    					map[it->first].count=sumlength;
    					map[it->first-1].count=sumlength;
    					it->second.left=true;
    					map[it->first-1].right=true;
    				}
    			}
    			if(it->second.right==false)
    			{
    				if(map.find(it->first+1)!=map.end() && map[it->first+1].left==false)
    				{
    					int sumlength=map[it->first].count+map[it->first+1].count;
    					map[it->first].count=sumlength;
    					map[it->first+1].count=sumlength;
    					it->second.right=true;
    					map[it->first+1].left=true;
    				}
    			}
    		}
    
    		it=map.begin();
    		int max=it->second.count;
    		for(it=map.begin();it!=map.end();it++)
    		{
    			if(max<it->second.count)
    				max=it->second.count;
    		}
    		return max;
    }
    };
    

    I test it right on my local PC, but run wrong on OJ on this sample

    Input: [1,3,5,2,4]
    Output: 4
    Expected: 5

    So I don't know if it is correct to define a struct for this submission, my PC get 5, but on OJ, it get 4. I don't know why? Could anybody help me to explain it? thanks a lot.


  • 0
    S

    Please tell the idea of this code. It doesn't look super straight forward anyway.


  • 0
    S

    Catch it!

    Using std::map<int,length> instead of unordered_map. I am not sure about what the version of cpp you are using. I would say it is not same as our FAQ mentioned. However, as I far as I know, unordered_map won't make its key in order. This for(it=map.begin();it!=map.end();it++) won't work like a charm as a result.

    Follow up, time complexity of std::map<int,length> is more than unordered_map. If I remember correctly, there is an elegant solution of this problem by getting rid of anything complex data structure.


  • 0
    R

    I want to create hashtable, and then traverse each element, by merge neighbour element. The problem is longest consecutive elements. I don;t know it do not show what's the problem is, as I have choose the problem id ahead


  • 0
    R

    It does not need to be key in order in my algorithm. I don't think hash table is complex, also map may exceed the time limited. Do you mean using radix sort instead of hash table? Why not support C++ 11? It's very useful! I can use command "g++ -o Longest LongestConsecutiveSeq.cpp -I. -std=c++0x" to compile it with C++11, but I can not choose the compile parameter in the leetcode server..... But I have get AC by using map, as it is not too strict for time : )


  • 0
    T

    leetcode supports unordered_map, I assure you. I wonder whether we are allowed to use Boost.


  • 0
    R

    Are you sure? Do you mean that you got ACs by using unordered_map? But how to explain my case, I got AC by using map instead of unordered_map?
    Also I am not sure whether boost are available, I don't think it's easy to use : )


  • 0
    T

    I am quite sure, because my solution using ordered_map to the problem "Max points on a line" passed the test. So it supports C++11. The type declaration is as follows:
    typedef unordered_map<float, int> map;
    For using those facilities in Boost that don't require compilation, you'll find it's the same way using STL.
    For example, if you want to employ unordered_map: #include <boost/unordered_map.hpp>.
    Leetcode Judge is not rigorous. I even passed this question using sort(), which was totally wrong.


  • 0
    R

    max points on a line has the lowest ac rate? Do you ac all problems?


  • 0
    T

    No, not at all. I just finished 14 problems. I like using "pick one" to pick a problem to practice. It happend that the system picked that question for me.


Log in to reply
 

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