Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit3718532

Browse files
add a solution for 128
1 parente338d1d commit3718532

File tree

2 files changed

+44
-5
lines changed

2 files changed

+44
-5
lines changed

‎src/main/java/com/fishercoder/solutions/_128.java

Lines changed: 41 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2,8 +2,10 @@
22

33
importjava.util.HashMap;
44
importjava.util.HashSet;
5+
importjava.util.Iterator;
56
importjava.util.Map;
67
importjava.util.Set;
8+
importjava.util.TreeSet;
79

810
publicclass_128 {
911
publicstaticclassSolution1 {
@@ -104,19 +106,22 @@ public int longestConsecutive(int[] nums) {
104106
}
105107

106108
publicstaticclassSolution3 {
109+
/**
110+
* O(n) time complexity.
111+
*/
107112
publicintlongestConsecutive(int[]nums) {
108-
HashSet<Integer>numSet =newHashSet<>();
113+
Set<Integer>set =newHashSet<>();
109114
for (intnum :nums) {
110-
numSet.add(num);
115+
set.add(num);
111116
}
112117

113118
intlongestStreak =0;
114-
for (intnum :nums) {
115-
if (!numSet.contains(num -1)) {
119+
for (intnum :set) {//we'll go through this set instead of nums, this makes a big difference in time complexity, esp. based on LeetCode test cases
120+
if (!set.contains(num -1)) {
116121
intcurrentNum =num;
117122
intcurrentStreak =1;
118123

119-
while (numSet.contains(currentNum +1)) {
124+
while (set.contains(currentNum +1)) {
120125
currentNum +=1;
121126
currentStreak +=1;
122127
}
@@ -126,4 +131,35 @@ public int longestConsecutive(int[] nums) {
126131
returnlongestStreak;
127132
}
128133
}
134+
135+
publicstaticclassSolution4 {
136+
/**
137+
* O(nlogn) time complexity
138+
*/
139+
publicintlongestConsecutive(int[]nums) {
140+
if (nums.length ==0) {
141+
return0;
142+
}
143+
TreeSet<Integer>treeSet =newTreeSet<>();
144+
for (inti :nums) {
145+
treeSet.add(i);//O(logn) time complexity for each add() call
146+
}
147+
intans =1;
148+
Iterator<Integer>it =treeSet.iterator();
149+
Integercurr =it.next();
150+
intlen =1;
151+
while (it.hasNext()) {
152+
Integernext =it.next();
153+
if (curr +1 ==next) {
154+
len++;
155+
}else {
156+
len =1;
157+
}
158+
curr =next;
159+
ans =Math.max(ans,len);
160+
}
161+
ans =Math.max(ans,len);
162+
returnans;
163+
}
164+
}
129165
}

‎src/test/java/com/fishercoder/_128Test.java

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,16 +8,19 @@
88

99
publicclass_128Test {
1010
privatestatic_128.Solution3solution3;
11+
privatestatic_128.Solution4solution4;
1112
privatestaticint[]nums;
1213

1314
@BeforeClass
1415
publicstaticvoidsetup() {
1516
solution3 =new_128.Solution3();
17+
solution4 =new_128.Solution4();
1618
}
1719

1820
@Test
1921
publicvoidtest1() {
2022
nums =newint[]{100,4,200,1,3,2};
2123
assertEquals(4,solution3.longestConsecutive(nums));
24+
assertEquals(4,solution4.longestConsecutive(nums));
2225
}
2326
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp