algorithms/leetcode/array/longestConsecutive.go at master · TTWShell/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/* https://leetcode.com/problems/longest-consecutive-sequence/
Given an unsorted array of integers,
find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

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

package larray

func longestConsecutive(nums []int) int {
	length := len(nums)
	if length < 2 {
		return length
	}

	cache := make(map[int]bool, length)
	for _, num := range nums {
		cache[num] = false
	}

	max := 1
	for _, num := range nums {
		if used := cache[num]; used {
			continue
		}
		cache[num] = true
		left, right := num, num
		for left = num - 1; ; left-- {
			if used, ok := cache[left]; ok && !used {
				cache[left] = true
			} else {
				left++
				break
			}
		}
		for right = num + 1; ; right++ {
			if used, ok := cache[right]; ok && !used {
				cache[right] = true
			} else {
				right--
				break
			}
		}
		if tmp := right - left + 1; tmp > max {
			max = tmp
		}
	}
	return max
}

// import (
// 	unionfind  "github.com/TTWShell/algorithms/data-structure/union-find"
// )

// func longestConsecutive(nums []int) int {
// 	if len(nums) == 0 {
// 		return 0
// 	}

// 	uf := unionfind.New()

// 	sets := make(map[int]bool, len(nums))
// 	for _, num := range nums {
// 		sets[num] = true
// 		uf.Union(num, num)
// 	}

// 	for _, num := range nums {
// 		if _, ok := sets[num-1]; ok {
// 			uf.Union(num-1, num)
// 		}
// 		if _, ok := sets[num+1]; ok {
// 			uf.Union(num+1, num)
// 		}
// 	}

// 	res := 0
// 	for _, count := range uf.SetCount() {
// 		if count > res {
// 			res = count
// 		}
// 	}
// 	return res
// }