One solution of mine


  • 0
    U
    class Solution:
    # @param num, a list of integer
    # @return an integer
    def longestConsecutive(self, nums):
        interval_dict={}  #store intervals like [a,b) where dict[a]=b, dict[b]=a
        num_set=set()  #record the nums seen so far
        for num in nums:
            if num not in num_set:
                num_set.add(num)
                if num in interval_dict:
                    if num+1 in interval_dict:
                        lower=interval_dict[num]
                        upper=interval_dict[num+1]
                        del interval_dict[num], interval_dict[num+1]
                        interval_dict[lower]=upper
                        interval_dict[upper]=lower
                    else:
                        lower=interval_dict[num]
                        del interval_dict[num]
                        interval_dict[num+1]=lower
                        interval_dict[lower]=num+1
                else:
                    if num+1 in interval_dict:
                        upper=interval_dict[num+1]
                        del interval_dict[num+1]
                        interval_dict[num]=upper
                        interval_dict[upper]=num
                    else:
                        interval_dict[num]=num+1
                        interval_dict[num+1]=num
        length=0
        for num1,num2 in interval_dict.items():
            length=max(length,num1-num2)
        return length

  • 0
    T

    A java solution

    public class Solution {
    public int longestConsecutive(int[] num) {

        int max_size = 0;
        HashMap<Integer, Integer> map  = new HashMap<Integer, Integer>();
        for(int i = 0 ; i < num.length; i++){
            map.put(new Integer(num[i]), null);
        }
        
        for(int i = 0; i < num.length; i++){
            if(map.containsKey(new Integer(num[i]))){
                int size = 1;
                // go down
                int x = num[i] - 1;
                while(map.containsKey(new Integer(x))){
                    map.remove(new Integer(x));
                    size++;
                    x--;
                }
                int y = num[i] + 1;
                // and go down
                while(map.containsKey(new Integer(y))){
                    map.remove(new Integer(y));
                    size++;
                    y++;
                }
                
                if(size > max_size)
                    max_size = size;
            }
        }
        return max_size;
    }
    

    }


  • 0
    B

    Hashset is enough, no need for key/value pair


  • 0
    S

    Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.


Log in to reply
 

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