FilesExpand file tree

 master

/

LongestConsecutiveSequence128.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

99 lines (86 loc) · 2.67 KB

 master

/

LongestConsecutiveSequence128.java

Copy path

Top

File metadata and controls

• Code
• Blame

99 lines (86 loc) · 2.67 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

92

93

94

95

96

97

98

99

/**

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

*

*/

public class LongestConsecutiveSequence128 {

public int longestConsecutive(int[] nums) {

if (nums == null || nums.length == 0) return 0;

Map<Integer, Range> ranges = new HashMap<>();

Set<Integer> found = new HashSet<>();

int res = 1;

for (int i=0; i<nums.length; i++) {

int val = nums[i];

if (found.contains(val)) continue;

found.add(val);

Range left = ranges.get(val-1);

Range right = ranges.get(val+1);

Range newRange = new Range(val, val);

if (left == null && right == null) {

ranges.put(val, newRange);

continue;

}

if (left == null) {

newRange.r = right.r;

ranges.remove(right.l);

} else if (right == null) {

newRange.l = left.l;

ranges.remove(left.r);

} else {

newRange.l = left.l;

newRange.r = right.r;

ranges.remove(left.r);

ranges.remove(right.l);

}

ranges.put(newRange.l, newRange);

ranges.put(newRange.r, newRange);

res = Math.max(res, newRange.r-newRange.l+1);

}

return res;

}

class Range {

int l;

int r;

Range (int l0,int r0) { l=l0; r=r0; }

}

public int longestConsecutive2(int[] nums) {

if (nums == null || nums.length == 0) return 0;

Arrays.sort(nums);

int res = 1;

int temp = 1;

for (int i = 1; i < nums.length; i++) {

if (nums[i] == nums[i-1]) continue;

if (nums[i] == nums[i-1]+1) {

temp += 1;

} else {

res = Math.max(res, temp);

temp = 1;

}

}

return Math.max(res, temp);

}

public int longestConsecutive3(int[] nums) {

if (nums == null || nums.length == 0) return 0;

Set<Integer> set = new HashSet<>();

for (int n : nums) set.add(n);

int res = 1;

for (int n : set) {

if (set.contains(n-1)) continue;

int curr = n;

int temp = 1;

while (set.contains(curr+1)) {

curr += 1;

temp += 1;

}

res = Math.max(res, temp);

}

return res;

}

}