|
5 | 5 | importjava.util.Map; |
6 | 6 | importjava.util.Set; |
7 | 7 |
|
8 | | -/** |
9 | | - * 128. Longest Consecutive Sequence |
10 | | -
|
11 | | - Given an unsorted array of integers, find the length of the longest consecutive elements sequence. |
12 | | -
|
13 | | - For example, |
14 | | - Given [100, 4, 200, 1, 3, 2], |
15 | | - The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4. |
16 | | -
|
17 | | - Your algorithm should run in O(n) complexity. |
18 | | - */ |
19 | 8 | publicclass_128 { |
20 | | -publicstaticclassSolution1 { |
21 | | -publicintlongestConsecutive(int[]nums) { |
22 | | -Map<Integer,Integer>map =newHashMap(); |
23 | | -//<value, index> |
24 | | -UnionFinduf =newUnionFind(nums); |
25 | | -for (inti =0;i <nums.length;i++) { |
26 | | -if (map.containsKey(nums[i])) { |
27 | | -continue; |
| 9 | +publicstaticclassSolution1 { |
| 10 | +publicintlongestConsecutive(int[]nums) { |
| 11 | +Map<Integer,Integer>map =newHashMap(); |
| 12 | +//<value, index> |
| 13 | +UnionFinduf =newUnionFind(nums); |
| 14 | +for (inti =0;i <nums.length;i++) { |
| 15 | +if (map.containsKey(nums[i])) { |
| 16 | +continue; |
| 17 | + } |
| 18 | +map.put(nums[i],i); |
| 19 | +if (map.containsKey(nums[i] -1)) { |
| 20 | +uf.union(i,map.get(nums[i] -1)); |
| 21 | +//note: we want to union this index and nums[i]-1's root index which we can get from the map |
| 22 | + } |
| 23 | +if (map.containsKey(nums[i] +1)) { |
| 24 | +uf.union(i,map.get(nums[i] +1)); |
| 25 | + } |
| 26 | + } |
| 27 | +returnuf.maxUnion(); |
28 | 28 | } |
29 | | -map.put(nums[i],i); |
30 | | -if (map.containsKey(nums[i] -1)) { |
31 | | -uf.union(i,map.get(nums[i] -1)); |
32 | | -//note: we want to union this index and nums[i]-1's root index which we can get from the map |
33 | | - } |
34 | | -if (map.containsKey(nums[i] +1)) { |
35 | | -uf.union(i,map.get(nums[i] +1)); |
36 | | - } |
37 | | - } |
38 | | -returnuf.maxUnion(); |
39 | | - } |
40 | 29 |
|
41 | | -classUnionFind { |
42 | | -int[]ids; |
43 | | - |
44 | | -publicUnionFind(int[]nums) { |
45 | | -ids =newint[nums.length]; |
46 | | -for (inti =0;i <nums.length;i++) { |
47 | | -ids[i] =i; |
48 | | - } |
49 | | - } |
50 | | - |
51 | | -publicvoidunion(inti,intj) { |
52 | | -intx =find(ids,i); |
53 | | -inty =find(ids,j); |
54 | | -ids[x] =y; |
55 | | - } |
56 | | - |
57 | | -publicintfind(int[]ids,inti) { |
58 | | -while (i !=ids[i]) { |
59 | | -ids[i] =ids[ids[i]]; |
60 | | -i =ids[i]; |
61 | | - } |
62 | | -returni; |
63 | | - } |
64 | | - |
65 | | -publicbooleanconnected(inti,intj) { |
66 | | -returnfind(ids,i) ==find(ids,j); |
67 | | - } |
68 | | - |
69 | | -publicintmaxUnion() { |
70 | | -//this is O(n) |
71 | | -intmax =0; |
72 | | -int[]count =newint[ids.length]; |
73 | | -for (inti =0;i <ids.length;i++) { |
74 | | -count[find(ids,i)]++; |
75 | | -max =max <count[find(ids,i)] ?count[find(ids,i)] :max; |
| 30 | +classUnionFind { |
| 31 | +int[]ids; |
| 32 | + |
| 33 | +publicUnionFind(int[]nums) { |
| 34 | +ids =newint[nums.length]; |
| 35 | +for (inti =0;i <nums.length;i++) { |
| 36 | +ids[i] =i; |
| 37 | + } |
| 38 | + } |
| 39 | + |
| 40 | +publicvoidunion(inti,intj) { |
| 41 | +intx =find(ids,i); |
| 42 | +inty =find(ids,j); |
| 43 | +ids[x] =y; |
| 44 | + } |
| 45 | + |
| 46 | +publicintfind(int[]ids,inti) { |
| 47 | +while (i !=ids[i]) { |
| 48 | +ids[i] =ids[ids[i]]; |
| 49 | +i =ids[i]; |
| 50 | + } |
| 51 | +returni; |
| 52 | + } |
| 53 | + |
| 54 | +publicbooleanconnected(inti,intj) { |
| 55 | +returnfind(ids,i) ==find(ids,j); |
| 56 | + } |
| 57 | + |
| 58 | +publicintmaxUnion() { |
| 59 | +//this is O(n) |
| 60 | +intmax =0; |
| 61 | +int[]count =newint[ids.length]; |
| 62 | +for (inti =0;i <ids.length;i++) { |
| 63 | +count[find(ids,i)]++; |
| 64 | +max =max <count[find(ids,i)] ?count[find(ids,i)] :max; |
| 65 | + } |
| 66 | +returnmax; |
| 67 | + } |
76 | 68 | } |
77 | | -returnmax; |
78 | | - } |
79 | 69 | } |
80 | | - } |
81 | | - |
82 | | -publicstaticclassSolution2 { |
83 | | -//inspired by this solution: https://discuss.leetcode.com/topic/25493/simple-fast-java-solution-using-set |
84 | | -publicintlongestConsecutive(int[]nums) { |
85 | | -if (nums ==null ||nums.length ==0) { |
86 | | -return0; |
87 | | - } |
88 | | - |
89 | | -Set<Integer>set =newHashSet(); |
90 | | -for (inti :nums) { |
91 | | -set.add(i); |
92 | | - } |
93 | | -intmax =1; |
94 | | - |
95 | | -for (intnum :nums) { |
96 | | -if (set.remove(num)) { |
97 | | -intval =num; |
98 | | -intcount =1; |
99 | | -while (set.remove(val -1)) { |
100 | | -val--;//we find all numbers that are smaller than num and remove them from the set |
101 | | - } |
102 | | -count +=num -val; |
103 | | - |
104 | | -val =num; |
105 | | -while (set.remove(val +1)) { |
106 | | -val++;//then we find all numbers that are bigger than num and also remove them from the set |
107 | | - } |
108 | | -count +=val -num; |
109 | | - |
110 | | -max =Math.max(max,count); |
| 70 | + |
| 71 | +publicstaticclassSolution2 { |
| 72 | +//inspired by this solution: https://discuss.leetcode.com/topic/25493/simple-fast-java-solution-using-set |
| 73 | +publicintlongestConsecutive(int[]nums) { |
| 74 | +if (nums ==null ||nums.length ==0) { |
| 75 | +return0; |
| 76 | + } |
| 77 | + |
| 78 | +Set<Integer>set =newHashSet(); |
| 79 | +for (inti :nums) { |
| 80 | +set.add(i); |
| 81 | + } |
| 82 | +intmax =1; |
| 83 | + |
| 84 | +for (intnum :nums) { |
| 85 | +if (set.remove(num)) { |
| 86 | +intval =num; |
| 87 | +intcount =1; |
| 88 | +while (set.remove(val -1)) { |
| 89 | +val--;//we find all numbers that are smaller than num and remove them from the set |
| 90 | + } |
| 91 | +count +=num -val; |
| 92 | + |
| 93 | +val =num; |
| 94 | +while (set.remove(val +1)) { |
| 95 | +val++;//then we find all numbers that are bigger than num and also remove them from the set |
| 96 | + } |
| 97 | +count +=val -num; |
| 98 | + |
| 99 | +max =Math.max(max,count); |
| 100 | + } |
| 101 | + } |
| 102 | +returnmax; |
111 | 103 | } |
112 | | - } |
113 | | -returnmax; |
114 | 104 | } |
115 | | - } |
116 | | - |
117 | | -publicstaticclassSolution3 { |
118 | | -publicintlongestConsecutive(int[]nums) { |
119 | | -HashSet<Integer>numSet =newHashSet<>(); |
120 | | -for (intnum :nums) { |
121 | | -numSet.add(num); |
122 | | - } |
123 | | - |
124 | | -intlongestStreak =0; |
125 | | -for (intnum :nums) { |
126 | | -if (!numSet.contains(num -1)) { |
127 | | -intcurrentNum =num; |
128 | | -intcurrentStreak =1; |
129 | | - |
130 | | -while (numSet.contains(currentNum +1)) { |
131 | | -currentNum +=1; |
132 | | -currentStreak +=1; |
133 | | - } |
134 | | -longestStreak =Math.max(longestStreak,currentStreak); |
| 105 | + |
| 106 | +publicstaticclassSolution3 { |
| 107 | +publicintlongestConsecutive(int[]nums) { |
| 108 | +HashSet<Integer>numSet =newHashSet<>(); |
| 109 | +for (intnum :nums) { |
| 110 | +numSet.add(num); |
| 111 | + } |
| 112 | + |
| 113 | +intlongestStreak =0; |
| 114 | +for (intnum :nums) { |
| 115 | +if (!numSet.contains(num -1)) { |
| 116 | +intcurrentNum =num; |
| 117 | +intcurrentStreak =1; |
| 118 | + |
| 119 | +while (numSet.contains(currentNum +1)) { |
| 120 | +currentNum +=1; |
| 121 | +currentStreak +=1; |
| 122 | + } |
| 123 | +longestStreak =Math.max(longestStreak,currentStreak); |
| 124 | + } |
| 125 | + } |
| 126 | +returnlongestStreak; |
135 | 127 | } |
136 | | - } |
137 | | -returnlongestStreak; |
138 | 128 | } |
139 | | - } |
140 | 129 | } |