PHP-最长连续序列

最长连续序列

题意

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

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

解题思路：

不能排序，该题目要求时间复杂度，则以空间换时间，线性遍历一次入哈希，查找，更新 O(n)， 线性第二次遍历通过每一个值（-1）定位哈希槽，判断是否连续序列，如果是则向后不断遍历（+1） 直到不存在 O(n)，向后遍历的同时累加序列长度， 以此类推， 直到选出最长序列， 总时间复杂度应该是 O(n+n) = O(n)

代码

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function longestConsecutive($nums) {
        $max  = 0;
        $hash = [];
        foreach ($nums as $val) {
            $hash[$val] = 1;
        }
        foreach ($nums as $val){
            $num = 1;
            if (!$hash[$val - 1]) {
                while($hash[++$val]) $num++;
            }
            $max = $num > $max ? $num : $max;
        }
        return $max;
    }
}

测试

  $obj  = new Solution();

  $nums = [100,200,405,101,450,102];
  print_r($obj->longestConsecutive($nums)); // 3 【100，101，102】

  $nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1];
  print_r($obj->longestConsecutive($nums)); // 9 【0，1，2，3，4，5，6，7，8】