128. 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.

思路

排序之后，数连续个数即可。由于不知道数的范围（太大）, 最优的效率也只是 \(O(n\log n)\)

如果能对每个数以及相邻数以 \(O(1)\) 进行快速查找, 就可以在 \(O(n)\) 知道每个连续分区的长度，从而知道最长的。

所以考虑用hash来存储做查找即可。

代码

# @param {Integer[]} nums
# @return {Integer}
def longest_consecutive(nums)
  set = Hash[*nums.map{ |p| [p, true]}.flatten]
  m = 0
  until set.empty?
    i, _ = set.shift
    size = 1 + findForward(set,i-1,0) + findBackward(set, i+1,0)
    m = size if m < size
  end
  m
end

def findForward(set, c, num)
  set.delete(c) ? findForward(set,c-1,num+1) : num
end

def findBackward(set, c, num)
  set.delete(c) ? findBackward(set,c+1,num+1) : num
end