Can we use sort() to solve this question?


  • 0
    C

    If I use sort(), can I say my algorithm is O(n) ?
    Thanks.

        bool compareVec( const int& a, const int& b) {
    	return a < b;
    }
    int longestConsecutive(vector<int> &num) {
    	int size = num.size();
        if( size < 2 )
    		return size;
        sort( num.begin(), num.end(), compareVec );
        int len = 1;
        int flag = 1;
        for( int i = 1; i < size; ++i ) {
    		if( num[i] - num[i-1] == 1 ) {
    			flag++;   
            } else {
    			if( flag > len ) {
    				len = flag;
                }
                flag = 1;
            }
    	}
        if( flag > len ) {
    		len = flag;
        }
        return len;
    }

  • 0
    S

    Using sort() will never be O(N), since it takes O(N log N).

    When calculating time complexity, do not leave library function out.


  • 0
    T

    I just don't see why you define the function compareVec(), regarding that the elements contained in the vector are of type int. sort() will naturally use operator < to sort out the vector, won't it?
    Besides, I also have some doubts about 'const int & a'. I agree with const, but I don't think it bothers using reference for an int.
    As for sort, I tried it, and leetcode let it pass the test. However, as mentioned by shangrila, it does absolutely not satisfy the requirement.


Log in to reply
 

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