Skip to content

Latest commit

 

History

History
378 lines (327 loc) · 8.2 KB

README_EN.md

File metadata and controls

378 lines (327 loc) · 8.2 KB

128. Longest Consecutive Sequence

中文文档

Description

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

 

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

 

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Solutions

Solution 1: Sorting

First, we sort the array, and use a variable $t$ to record the length of the current continuous sequence, and use a variable $ans$ to record the length of the longest continuous sequence.

Then, we start to traverse the array from index $i=1$, for the current element $nums[i]$:

  • If $nums[i]=nums[i-1]$ , then the current element is duplicate, and we don't need to consider it;
  • If $nums[i]=nums[i-1]+1$ , then the current element can be connected to the previous continuous sequence to form a longer continuous sequence, so we update $t = t + 1$ and update the answer $ans = \max(ans, t)$;
  • Otherwise, the current element cannot be connected to the previous continuous sequence, so we reset $t$ to $1$.

Finally, we return the answer $ans$.

Time complexity $O(n \times \log n)$, space complexity $O(\log n)$, where $n$ is the length of the array.

Solution 2: Hash Table

We use a hash table to store all the elements in the array, and then we traverse the array to find the longest continuous sequence for each element $x$. If the predecessor of the current element $x-1$ is not in the hash table, we use the current element as the starting point, and keep trying to match $x+1, x+2, x+3, \dots$ until we cannot match, the matching length at this time is the length of the longest continuous sequence starting from $x$, so we update the answer.

Time complexity $O(n)$, space complexity $O(n)$, where $n$ is the length of the array.

Python3

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return n
        nums.sort()
        ans = t = 1
        for a, b in pairwise(nums):
            if a == b:
                continue
            if a + 1 == b:
                t += 1
                ans = max(ans, t)
            else:
                t = 1
        return ans
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        ans = 0
        for x in nums:
            if x - 1 not in s:
                y = x + 1
                while y in s:
                    y += 1
                ans = max(ans, y - x)
        return ans

Java

class Solution {
    public int longestConsecutive(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        Arrays.sort(nums);
        int ans = 1, t = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == nums[i - 1]) {
                continue;
            }
            if (nums[i] == nums[i - 1] + 1) {
                ans = Math.max(ans, ++t);
            } else {
                t = 1;
            }
        }
        return ans;
    }
}
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int x : nums) {
            s.add(x);
        }
        int ans = 0;
        for (int x : nums) {
            if (!s.contains(x - 1)) {
                int y = x + 1;
                while (s.contains(y)) {
                    ++y;
                }
                ans = Math.max(ans, y - x);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return n;
        }
        sort(nums.begin(), nums.end());
        int ans = 1, t = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == nums[i - 1]) {
                continue;
            }
            if (nums[i] == nums[i - 1] + 1) {
                ans = max(ans, ++t);
            } else {
                t = 1;
            }
        }
        return ans;
    }
};
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int ans = 0;
        for (int x : nums) {
            if (!s.count(x - 1)) {
                int y = x + 1;
                while (s.count(y)) {
                    y++;
                }
                ans = max(ans, y - x);
            }
        }
        return ans;
    }
};

Rust

use std::collections::HashSet;

impl Solution {
    #[allow(dead_code)]
    pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
        let mut s = HashSet::new();
        let mut ret = 0;

        // Initialize the set
        for num in &nums {
            s.insert(*num);
        }

        for num in &nums {
            if s.contains(&(*num - 1)) {
                continue;
            }
            let mut cur_num = num.clone();
            while s.contains(&cur_num) {
                cur_num  += 1;
            }
            // Update the answer
            ret = std::cmp::max(ret, cur_num - num);
        }

        ret
    }
}

Go

func longestConsecutive(nums []int) int {
	n := len(nums)
	if n < 2 {
		return n
	}
	sort.Ints(nums)
	ans, t := 1, 1
	for i, x := range nums[1:] {
		if x == nums[i] {
			continue
		}
		if x == nums[i]+1 {
			t++
			ans = max(ans, t)
		} else {
			t = 1
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func longestConsecutive(nums []int) (ans int) {
	s := map[int]bool{}
	for _, x := range nums {
		s[x] = true
	}
	for _, x := range nums {
		if !s[x-1] {
			y := x + 1
			for s[y] {
				y++
			}
			ans = max(ans, y-x)
		}
	}
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
    const n = nums.length;
    if (n < 2) {
        return n;
    }
    nums.sort((a, b) => a - b);
    let ans = 1;
    let t = 1;
    for (let i = 1; i < n; ++i) {
        if (nums[i] === nums[i - 1]) {
            continue;
        }
        if (nums[i] === nums[i - 1] + 1) {
            ans = Math.max(ans, ++t);
        } else {
            t = 1;
        }
    }
    return ans;
};
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
    const s = new Set(nums);
    let ans = 0;
    for (const x of nums) {
        if (!s.has(x - 1)) {
            let y = x + 1;
            while (s.has(y)) {
                y++;
            }
            ans = Math.max(ans, y - x);
        }
    }
    return ans;
};

TypeScript

function longestConsecutive(nums: number[]): number {
    const n = nums.length;
    if (n < 2) {
        return n;
    }
    let ans = 1;
    let t = 1;
    nums.sort((a, b) => a - b);
    for (let i = 1; i < n; ++i) {
        if (nums[i] === nums[i - 1]) {
            continue;
        }
        if (nums[i] === nums[i - 1] + 1) {
            ans = Math.max(ans, ++t);
        } else {
            t = 1;
        }
    }
    return ans;
}
function longestConsecutive(nums: number[]): number {
    const s: Set<number> = new Set(nums);
    let ans = 0;
    for (const x of s) {
        if (!s.has(x - 1)) {
            let y = x + 1;
            while (s.has(y)) {
                y++;
            }
            ans = Math.max(ans, y - x);
        }
    }
    return ans;
}

...