给定一个未排序的整数数组，找出最长连续序列的长度

 """

    
 给定一个未排序的整数数组，找出最长连续序列的长度
    
 eg:
    
 input: [100, 4, 200, 1, 3, 2]
    
 output: [1, 2, 3, 4]
    
 返回长度=4
    
 """
    
  
    
 import time
    
 import random
    
  
    
 from functools import wraps
    
  
    
  
    
 # 计算运行时间装饰器
    
 def time_cal_deco_(max_repeat: int):
    
     def time_cal_deco(func):
    
     @wraps(func)
    
     def inner(raw_list: list):
    
         t_begin = time.time()
    
         for i in range(max_repeat):
    
             res = func(raw_list)
    
         t_end = time.time()
    
         print(f'{func.__name__} time spent = {t_end - t_begin}s')
    
         return res
    
     return inner
    
     return time_cal_deco
    
  
    
  
    
 @time_cal_deco_(max_repeat=10)
    
 def find_longest_list(raw_list: list) -> int:
    
     """
    
     计算最长连续序列长度
    
     :param raw_list:
    
     :return:
    
     """
    
     # 对列表排序
    
     raw_list.sort()
    
     i = 0
    
     max_len = 1
    
     # 遍历列表，每一次遍历计算以该数字为起点的最长连续列表长度
    
     while i < len(raw_list):
    
     max_len_tmp = 1
    
     j = i + 1
    
     while (j < len(raw_list)) and (raw_list[j] - raw_list[j-1] == 1):
    
         j += 1
    
         max_len_tmp += 1
    
     max_len = max(max_len_tmp, max_len)
    
     i += 1
    
     return max_len
    
  
    
  
    
 @time_cal_deco_(max_repeat=10)
    
 def find_longest_list_v2(raw_list: list) -> int:
    
     """
    
     计算最长连续序列长度
    
     :param raw_list:
    
     :return:
    
     """
    
     # 标记列表中某个数字
    
     _dic = {x: 1 for x in raw_list}
    
     max_len = 0
    
     for num in raw_list:
    
     # 每次遍历初始化当前最大长度=1
    
     _len = 1
    
     if _dic.get(num):
    
         del _dic[num]
    
         num_left = num - 1
    
         num_right = num + 1
    
         while _dic.get(num_left):
    
             # 以当前数字为起点，依次向左、向右达到最左、最右
    
             del _dic[num_left]
    
             num_left -= 1
    
             # 每推进一次，当前长度+=1
    
             _len += 1
    
         while _dic.get(num_right):
    
             del _dic[num_right]
    
             num_right += 1
    
             _len += 1
    
         # 生成全局最大长度
    
         max_len = max(max_len, _len)
    
     return max_len
    
  
    
  
    
 if __name__ == '__main__':
    
     # 随机列表两种算法时间复杂度相当，但是顺序程度较高时，find_longest_list_v2性能更好
    
     # demo = list(set([random.randint(1, 2000000) for x in range(50000)]))
    
     demo = [x for x in range(1000)]
    
     print(len(demo))
    
     # m1 = find_longest_list([100, 4, 200, 1, 3, 2])
    
     # m2 = find_longest_list_v2([100, 4, 200, 1, 3, 2])
    
     m1 = find_longest_list(demo)
    
     m2 = find_longest_list_v2(demo)
    
     print(m1, m2)