This problem has a O(n) solution?


  • 0
    L

    I have no idea. can anyone give a hint? thank you very much.


  • 4
    J

    Use a set to contain all the number.
    And only contain the areas have not appeared consecutive sequence during the online computing.

    //about the question : the number appears more than once only count once. (Tried)
    public int longestConsecutive(int[] num) {
        if(num == null)
            return 0;
            
    	Set<Integer> set = new HashSet<Integer>();
    	int max = 1;
     
    	for (int n : num)
    		set.add(n);
     
    	for (int n : num) {
    		int count = 1, i = 0;
     
    		while (set.contains(n - ++i)) {
    			count ++;
    			set.remove(n - i);
    		}
    		
    		i = 0;
    		while (set.contains(n + ++i)) {
    			count ++;
    			set.remove(n + i);
    		}
     
    		max = Math.max(count, max);
    	}
     
    	return max;
    }

  • 1
    I

    The intuitive idea is to 'chain' the consecutive numbers together. To do this, we can set up a parent and a child pointer, i.e., parent[i] = j means the parent of num[i] is j. To be efficient, you need to use a hash map to map the value to its index in the array.

    After you construct the chain, given any number v of index i, you can simply, traverse parent/child to get the length of chain, and mark the elements as visited. Thus, each element will only be visited once.

    An improvement is to record the range directly. The code is given in another post.


  • 0
    G

    Set insertion and deletion can take 'O(n)' in the worst case making the time complexity of you algorithm 'O(n^2)'.


  • 0
    J

    Yeah, I really haven't think about the set's operation, the bad case is elements' HashMap.hash(Integer.hashCode()) value is same. But, perhaps there are few cases, and average cost is O(n).


  • 0
    H

    I agree, on average it is O(n)


  • 0
    R

    The hash give you O(1) only if there no repetitions on the result of the hash function.
    Given that hash(x) returns the same value for the same value of x by definition, if the element x is repeated twice you don't have O(1).

    Now if you insert N elements into the hash map that is not O(1), but O(1) or O(logN) depending on the implementation, you end up with something greater than O(N).


  • 2
    J
    1. RadixSort takes O(n) time.
    2. Scan a array to get the longest consecutive sequence takes O(n) time.
      so we can combine
    public int longestConsecutive(int[] num) {
        num = this.radixSort(num);
        int length = 1, clength = 1;
        for (int i = 1; i < num.length; i++) {
            if (num[i] == num[i - 1])
                continue;
            if (num[i] == num[i - 1] + 1) {
                clength++;
            } else {
                if (clength >= length) {
                    length = clength;
                }
                clength = 1;
            }
        }
        return clength > length ? clength : length;
    }
    
        int[] radixSort(int[] num) {
            int l = Integer.MIN_VALUE;
            for (int n : num) {
                if (Math.abs(n) > l)
                    l = Math.abs(n);
            }
            int base = 1;
    
            while (l / base != 0) {
                num = this.countSort(num, base);
                base *= 10;
            }
            return num;
        }
    
        private int[] countSort(int[] num, int base) {
            int[] psn = new int[num.length];
    
            int[] counts = new int[19];
            int[] indexes = new int[19];
            for (int n : num) {
                int tail = this.getTail(n, base);
                counts[tail] = counts[tail] + 1;
            }
    
            indexes[1] = counts[0];
            for (int i = 2; i < counts.length; i++) {
                indexes[i] = indexes[i - 1] + counts[i - 1];
            }
    
            for (int i = 0; i < num.length; i++) {
                int tail = this.getTail(num[i], base);
                int index = indexes[tail];
                psn[index] = num[i];
                indexes[tail] = index + 1;
            }
            return psn;
        }
    
        int getTail(int n, int base) {
            return ((n % (base * 10)) / base) + 9;
        }

  • 0
    B

    thanks for the algorithm! The only thing I would say is to check against Integer.MAX(MIN)_VALUE in the while loops.


Log in to reply
 

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