[LeetCode] 128. Longest Consecutive Sequence

 轉自LeetCode

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

Solution

題目是要找到在一個 array 中，連續數字的最長長度

一開始想用sliding window，但題目的 array 不是 sorted 的，看起來不可行

題目又要求 O(n) 的時間複雜度

能加速歷遍速度的，看起來要用到 hash map or hash set

這邊選擇使用 hash set，可以直接把重複數字的變因消除掉

然後因為從 4 往下找到 1，也就是 4 -> 3 -> 2 -> 1

和從 1 找到 4，也就是 1 -> 2 -> 3 -> 4，兩者是一樣的

所以一旦有找過，就可以移除掉

因此，每個數字，我們就往上和往下找，一旦在 set 裡面，移除並移動指標

過程中也記錄最大值

Kotlin

	class Solution {
	fun longestConsecutive(nums: IntArray): Int {
	val table = nums.toMutableSet()
	var ans = 0
	var down: Int
	var up: Int
	for(n in nums) {
	down = n - 1
	up = n + 1
	while(table.contains(down)) {
	table.remove(down)
	--down
	}
	while(table.contains(up)) {
	table.remove(up)
	++up
	}
	ans = Math.max(ans, up - down - 1)
	}
	return ans
	}
	}

view raw longest_consecutive_sequence.kt hosted with ❤ by GitHub