Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

class Solution {
public:
    int longestConsecutive(vector<int> &num) 
    {                  
        int n=num.size();
        vector<int> v1;
        vector<int> v2;        
        for(int i=0;i<n;i++)
            if(num[i]<0) v1.push_back(num[i]);
            else v2.push_back(num[i]);
        radixsort(v1);
        radixsort(v2);
        for(int i=0;i<v1.size();i++)
            num[i]=v1[v1.size()-i-1];
        for(int i=0;i<v2.size();i++)
            num[i+v1.size()]=v2[i];
        
        //get the longest
        int longest=1;
        int index=0;
        while(true)
        {
            if(index+1>=n) break;
            int con=1;
            int index2=index;
            while(index2+1<n && (num[index2+1]==num[index2] || num[index2+1]==num[index2]+1))
            {
                if(num[index2+1]==num[index2]+1) con++;
                index2++;
            }
            if(con>longest) longest=con;
            index=index2+1;                    
        }
        return longest;
    }

    void radixsort(vector<int> &num)
    {
        int n=num.size();
        int* data=(int*)malloc(n*sizeof(int));
        int d=1;
        int radix=10;
        int* bulk=(int*)malloc(radix*sizeof(int));
        //radix sort
        for(int k=0;k<10;k++)
        {
            for(int i=0;i<radix;i++) bulk[i]=0;
            for(int i=0;i<n;i++)
            {
                int ibulk=num[i]/d%radix;
                if(ibulk<0) ibulk=-ibulk;
                bulk[ibulk]++;
            }
                
            int step=bulk[0];
            bulk[0]=0;
            for(int i=1;i<radix;i++)
            {
                int step2=bulk[i];
                bulk[i]=bulk[i-1]+step;
                step=step2;
            }
            
            for(int i=0;i<n;i++)
            {
                int ibulk=num[i]/d%radix;
                if(ibulk<0) ibulk=-ibulk;
                data[bulk[ibulk]]=num[i];
                bulk[ibulk]++;
            }

            for(int i=0;i<n;i++)
                num[i]=data[i];
                
            d=d*radix;
        }
        free(data);
        free(bulk);
    }
};