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

Commit3271866

Browse files
committed
080 (3) two pointers to limit duplicates
1 parent61e9cfd commit3271866

File tree

8 files changed

+261
-203
lines changed

8 files changed

+261
-203
lines changed

‎src/_080_RemoveDuplicatesFromSortedArrayII/Solution.java‎

Lines changed: 16 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -23,18 +23,25 @@
2323
publicclassSolution {
2424

2525
publicintremoveDuplicates(int[]nums) {
26-
intlen =nums.length;
27-
if (len <=2) {
28-
returnlen;
26+
intj = -1;// last index of `good` part
27+
for (inti =0;i <nums.length;i++) {
28+
if (i <2 || (nums[i] !=nums[j -1])) {
29+
nums[++j] =nums[i];
30+
}
2931
}
30-
intlastValid =1;
31-
for (inti =2;i <len;i++) {
32-
if (nums[i] !=nums[lastValid] || (nums[i] !=nums[lastValid -1])) {
33-
lastValid++;
34-
nums[lastValid] =nums[i];
32+
returnj +1;
33+
}
34+
35+
// version2, use `continue` keyword
36+
publicintremoveDuplicates2(int[]nums) {
37+
intj = -1;
38+
for (inti =0;i <nums.length;i++) {
39+
if (i >=2 &&nums[i] ==nums[j] &&nums[i] ==nums[j -1]) {
40+
continue;
3541
}
42+
nums[++j] =nums[i];
3643
}
37-
returnlastValid +1;
44+
returnj +1;
3845
}
3946

4047
}

‎src/_080_RemoveDuplicatesFromSortedArrayII/SolutionGeneral.java‎

Lines changed: 14 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
/**
2-
* Time : O(); Space: O()
2+
* Time : O(N); Space: O(1)
33
* @tag : Array; Backtracking
44
* @by : Steven Cooks
55
* @date: Jun 7, 2015
@@ -28,33 +28,29 @@
2828

2929
/** see test {@link _080_RemoveDuplicatesFromSortedArrayII.SolutionGeneralTest } */
3030
publicclassSolutionGeneral {
31+
32+
privatestaticfinalintK =2;
3133

3234
publicintremoveDuplicates(int[]nums) {
33-
intk =2;
34-
returnremoveDuplicatesAtMostKDuplicates(nums,k);
35+
returnremoveDuplicatesAtMostKDuplicates(nums,K);
3536
}
3637

3738
// counting the number of duplicates of each number in array
38-
publicintremoveDuplicatesAtMostKDuplicates(int[]nums,intk) {
39-
intlen =nums.length;
40-
if (len <=k) {
41-
returnlen;
42-
}
43-
intlastValidIndex =0;
44-
intduplicates =1;
45-
for (inti =1;i <len;i++) {
46-
if (nums[i] !=nums[lastValidIndex]) {
39+
publicintremoveDuplicatesAtMostKDuplicates(int[]nums,intK) {
40+
intj = -1;// index of last valid elements
41+
intduplicates =0;
42+
for (inti =0;i <nums.length;i++) {
43+
if (i ==0 ||nums[i] !=nums[j]) {
4744
// first-time appeared number
48-
lastValidIndex++;
49-
nums[lastValidIndex] =nums[i];
45+
nums[++j] =nums[i];
5046
duplicates =1;
51-
}elseif (duplicates <k) {
52-
lastValidIndex++;
53-
nums[lastValidIndex] =nums[i];
47+
}elseif (duplicates <K) {
48+
nums[++j] =nums[i];
5449
duplicates++;
5550
}
51+
// ignore more than enough duplicates
5652
}
57-
returnlastValidIndex +1;
53+
returnj +1;
5854
}
5955

6056
}

src/_080_RemoveDuplicatesFromSortedArrayII/SolutionGeneral_2.java renamed to src/_080_RemoveDuplicatesFromSortedArrayII/SolutionGeneral2.java

Lines changed: 16 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -19,27 +19,27 @@
1919
*/
2020
package_080_RemoveDuplicatesFromSortedArrayII;
2121

22-
/** see test {@link _080_RemoveDuplicatesFromSortedArrayII.SolutionGeneral_2Test } */
23-
publicclassSolutionGeneral_2 {
22+
/** see test {@link _080_RemoveDuplicatesFromSortedArrayII.SolutionGeneral2Test } */
23+
publicclassSolutionGeneral2 {
24+
25+
// allowed number of duplicates
26+
privatestaticfinalintK =2;
2427

2528
publicintremoveDuplicates(int[]nums) {
26-
intk =2;
27-
returnremoveDuplicatesAtMostKDuplicates(nums,k);
29+
returnremoveDuplicatesAtMostKDuplicates(nums,K);
2830
}
2931

30-
publicintremoveDuplicatesAtMostKDuplicates(int[]nums,intk) {
31-
intlen =nums.length;
32-
if (len <=k) {
33-
returnlen;
34-
}
35-
intlastValidIndex =k -1;
36-
for (inti =k;i <len;i++) {
37-
// as long as nums[i] is different nums[lastValid - k + 1]
38-
// we can still insert nums[i] into valid part
39-
if (nums[i] !=nums[lastValidIndex -k +1]) {
40-
nums[++lastValidIndex] =nums[i];
32+
/**
33+
* As long as nums[i] is different nums[lastValid - K + 1]
34+
* we can still insert nums[i] into valid part
35+
*/
36+
publicintremoveDuplicatesAtMostKDuplicates(int[]nums,intK) {
37+
intj = -1;// index of last valid elements
38+
for (inti =0;i <nums.length;i++) {
39+
if (j -K +1 <0 ||nums[i] !=nums[j -K +1]) {
40+
nums[++j] =nums[i];
4141
}
4242
}
43-
returnlastValidIndex +1;
43+
returnj +1;
4444
}
4545
}

‎test/_080_RemoveDuplicatesFromSortedArrayII/PracticeTest.java‎

Lines changed: 31 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -28,12 +28,25 @@ public void tearDown() throws Exception {
2828
solution =null;
2929
}
3030

31+
32+
@Test
33+
publicvoidTest0() {
34+
int[]nums = { };
35+
intactual =solution.removeDuplicates(nums);
36+
intexpected =0;
37+
assertEquals(expected,actual);
38+
39+
// the part after expected length does not matter
40+
int[]expecteds = { };
41+
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
42+
}
43+
3144
@Test
3245
publicvoidTest1() {
3346
int[]nums = {1,1,1,2,2,3 };
3447
intactual =solution.removeDuplicates(nums);
3548
intexpected =5;
36-
assertEquals(Arrays.toString(nums),expected,actual);
49+
assertEquals(expected,actual);
3750

3851
// the part after expected length does not matter
3952
int[]expecteds = {1,1,2,2,3 };
@@ -45,7 +58,7 @@ public void Test2() {
4558
int[]nums = {1,1,1,2,2,3,3,3 };
4659
intactual =solution.removeDuplicates(nums);
4760
intexpected =6;
48-
assertEquals(Arrays.toString(nums),expected,actual);
61+
assertEquals(expected,actual);
4962

5063
int[]expecteds = {1,1,2,2,3,3 };
5164
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
@@ -56,7 +69,7 @@ public void Test3() {
5669
int[]nums = {1,2,3,4,4,4 };
5770
intactual =solution.removeDuplicates(nums);
5871
intexpected =5;
59-
assertEquals(Arrays.toString(nums),expected,actual);
72+
assertEquals(expected,actual);
6073

6174
int[]expecteds = {1,2,3,4,4 };
6275
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
@@ -67,7 +80,7 @@ public void Test4() {
6780
int[]nums = {1,2,3,4,4,4,5,5 };
6881
intactual =solution.removeDuplicates(nums);
6982
intexpected =7;
70-
assertEquals(Arrays.toString(nums),expected,actual);
83+
assertEquals(expected,actual);
7184

7285
int[]expecteds = {1,2,3,4,4,5,5 };
7386
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
@@ -78,7 +91,7 @@ public void Test5() {
7891
int[]nums = {1,1,1,2,3,4,5 };
7992
intactual =solution.removeDuplicates(nums);
8093
intexpected =6;
81-
assertEquals(Arrays.toString(nums),expected,actual);
94+
assertEquals(expected,actual);
8295

8396
int[]expecteds = {1,1,2,3,4,5 };
8497
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
@@ -89,7 +102,7 @@ public void Test6() {
89102
int[]nums = {1,1 };
90103
intactual =solution.removeDuplicates(nums);
91104
intexpected =2;
92-
assertEquals(Arrays.toString(nums),expected,actual);
105+
assertEquals(expected,actual);
93106

94107
int[]expecteds = {1,1 };
95108
assertArrayEquals(expecteds,nums);
@@ -100,10 +113,21 @@ public void Test7() {
100113
int[]nums = {1,2,2 };
101114
intactual =solution.removeDuplicates(nums);
102115
intexpected =3;
103-
assertEquals(Arrays.toString(nums),expected,actual);
116+
assertEquals(expected,actual);
104117

105118
int[]expecteds = {1,2,2 };
106119
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
107120
}
108121

122+
@Test
123+
publicvoidTest8() {
124+
int[]nums = {1 };
125+
intactual =solution.removeDuplicates(nums);
126+
intexpected =1;
127+
assertEquals(expected,actual);
128+
129+
int[]expecteds = {1 };
130+
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
131+
}
132+
109133
}
Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
package_080_RemoveDuplicatesFromSortedArrayII;
2+
3+
importstaticorg.junit.Assert.*;
4+
5+
importjava.util.Arrays;
6+
7+
importorg.junit.After;
8+
importorg.junit.Before;
9+
importorg.junit.Test;
10+
11+
publicclassSolutionGeneral2Test {
12+
13+
/** Test solution {@Link _080_RemoveDuplicatesFromSortedArrayII.SolutionGeneral2 } */
14+
SolutionGeneral2solution;
15+
16+
@Before
17+
publicvoidsetUp()throwsException {
18+
solution =newSolutionGeneral2();
19+
}
20+
21+
@After
22+
publicvoidtearDown()throwsException {
23+
solution =null;
24+
}
25+
26+
27+
@Test
28+
publicvoidTest0() {
29+
int[]nums = { };
30+
intactual =solution.removeDuplicates(nums);
31+
intexpected =0;
32+
assertEquals(expected,actual);
33+
34+
// the part after expected length does not matter
35+
int[]expecteds = { };
36+
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
37+
}
38+
39+
@Test
40+
publicvoidTest1() {
41+
int[]nums = {1,1,1,2,2,3 };
42+
intactual =solution.removeDuplicates(nums);
43+
intexpected =5;
44+
assertEquals(expected,actual);
45+
46+
// the part after expected length does not matter
47+
int[]expecteds = {1,1,2,2,3 };
48+
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
49+
}
50+
51+
@Test
52+
publicvoidTest2() {
53+
int[]nums = {1,1,1,2,2,3,3,3 };
54+
intactual =solution.removeDuplicates(nums);
55+
intexpected =6;
56+
assertEquals(expected,actual);
57+
58+
int[]expecteds = {1,1,2,2,3,3 };
59+
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
60+
}
61+
62+
@Test
63+
publicvoidTest3() {
64+
int[]nums = {1,2,3,4,4,4 };
65+
intactual =solution.removeDuplicates(nums);
66+
intexpected =5;
67+
assertEquals(expected,actual);
68+
69+
int[]expecteds = {1,2,3,4,4 };
70+
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
71+
}
72+
73+
@Test
74+
publicvoidTest4() {
75+
int[]nums = {1,2,3,4,4,4,5,5 };
76+
intactual =solution.removeDuplicates(nums);
77+
intexpected =7;
78+
assertEquals(expected,actual);
79+
80+
int[]expecteds = {1,2,3,4,4,5,5 };
81+
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
82+
}
83+
84+
@Test
85+
publicvoidTest5() {
86+
int[]nums = {1,1,1,2,3,4,5 };
87+
intactual =solution.removeDuplicates(nums);
88+
intexpected =6;
89+
assertEquals(expected,actual);
90+
91+
int[]expecteds = {1,1,2,3,4,5 };
92+
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
93+
}
94+
95+
@Test
96+
publicvoidTest6() {
97+
int[]nums = {1,1 };
98+
intactual =solution.removeDuplicates(nums);
99+
intexpected =2;
100+
assertEquals(expected,actual);
101+
102+
int[]expecteds = {1,1 };
103+
assertArrayEquals(expecteds,nums);
104+
}
105+
106+
@Test
107+
publicvoidTest7() {
108+
int[]nums = {1,2,2 };
109+
intactual =solution.removeDuplicates(nums);
110+
intexpected =3;
111+
assertEquals(expected,actual);
112+
113+
int[]expecteds = {1,2,2 };
114+
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
115+
}
116+
117+
@Test
118+
publicvoidTest8() {
119+
int[]nums = {1 };
120+
intactual =solution.removeDuplicates(nums);
121+
intexpected =1;
122+
assertEquals(expected,actual);
123+
124+
int[]expecteds = {1 };
125+
assertArrayEquals(expecteds,Arrays.copyOf(nums,actual));
126+
}
127+
128+
}

0 commit comments

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