Commit03a832a

committed

add 1539

1 parent4e16197 commit03a832aCopy full SHA for 03a832a

File tree

+112

-0

lines changed

README.md
src
- main/java/com/fishercoder/solutions
  - _1539.java
- test/java/com/fishercoder
  - _1539Test.java

+112

-0

lines changed

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ ★`
`8`	`8`
`9`	`9`	`\| # \| Title \| Solutions \| Video \| Difficulty \| Tag`
`10`	`10`	`\|-----\|----------------\|---------------\|--------\|-------------\|-------------`
	`11`	`+\|1539\|[Kth Missing Positive Number](https://leetcode.com/problems/kth-missing-positive-number/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1539.java)\|\|Medium\|Array, HashTable\|`
`11`	`12`	`\|1535\|[Find the Winner of an Array Game](https://leetcode.com/problems/find-the-winner-of-an-array-game/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1535.java)\|[:tv:](https://youtu.be/v6On1TQfMTU)\|Medium\|Array\|`
`12`	`13`	`\|1534\|[Count Good Triplets](https://leetcode.com/problems/count-good-triplets/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1534.java)\|\|Easy\|Array\|`
`13`	`14`	`\|1528\|[Shuffle String](https://leetcode.com/problems/shuffle-string/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1528.java)\|\|Easy\|Sort\|`

Lines changed: 67 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,67 @@`
	`1`	`+packagecom.fishercoder.solutions;`
	`2`	`+`
	`3`	`+importjava.util.HashSet;`
	`4`	`+importjava.util.Set;`
	`5`	`+`
	`6`	`+publicclass_1539 {`
	`7`	`+publicstaticclassSolution1 {`
	`8`	`+/**`
	`9`	`+ * Space: O(n)`
	`10`	`+ * Time: O(n)`
	`11`	`+ */`
	`12`	`+publicintfindKthPositive(int[]arr,intk) {`
	`13`	`+Set<Integer>set =newHashSet<>();`
	`14`	`+intmax =0;`
	`15`	`+for (inti :arr) {`
	`16`	`+set.add(i);`
	`17`	`+max =Math.max(max,i);`
	`18`	`+ }`
	`19`	`+intmissed =0;`
	`20`	`+for (inti =1;i <=max;i++) {`
	`21`	`+if (!set.contains(i)) {`
	`22`	`+missed++;`
	`23`	`+ }`
	`24`	`+if (missed ==k) {`
	`25`	`+returni;`
	`26`	`+ }`
	`27`	`+ }`
	`28`	`+while (missed++ <k) {`
	`29`	`+max++;`
	`30`	`+ }`
	`31`	`+returnmax;`
	`32`	`+ }`
	`33`	`+ }`
	`34`	`+`
	`35`	`+publicstaticclassSolution2 {`
	`36`	`+/**`
	`37`	`+ * Space: O(1)`
	`38`	`+ * Time: O(n)`
	`39`	`+ */`
	`40`	`+publicintfindKthPositive(int[]arr,intk) {`
	`41`	`+intmissed =0;`
	`42`	`+for (inti =0;i <arr.length;i++) {`
	`43`	`+if (i ==0) {`
	`44`	`+missed +=arr[0] -1;`
	`45`	`+if (missed >=k) {`
	`46`	`+returnk;`
	`47`	`+ }`
	`48`	`+ }else {`
	`49`	`+missed +=arr[i] -arr[i -1] -1;`
	`50`	`+if (missed >=k) {`
	`51`	`+missed -=arr[i] -arr[i -1] -1;`
	`52`	`+intresult =arr[i -1];`
	`53`	`+while (missed++ <k) {`
	`54`	`+result++;`
	`55`	`+ }`
	`56`	`+returnresult;`
	`57`	`+ }`
	`58`	`+ }`
	`59`	`+ }`
	`60`	`+intresult =arr[arr.length -1];`
	`61`	`+while (missed++ <k) {`
	`62`	`+result++;`
	`63`	`+ }`
	`64`	`+returnresult;`
	`65`	`+ }`
	`66`	`+ }`
	`67`	`+}`

Lines changed: 44 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,44 @@`
	`1`	`+packagecom.fishercoder;`
	`2`	`+`
	`3`	`+importcom.fishercoder.solutions._1539;`
	`4`	`+importorg.junit.BeforeClass;`
	`5`	`+importorg.junit.Test;`
	`6`	`+`
	`7`	`+importstaticjunit.framework.TestCase.assertEquals;`
	`8`	`+`
	`9`	`+publicclass_1539Test {`
	`10`	`+privatestatic_1539.Solution1solution1;`
	`11`	`+privatestatic_1539.Solution2solution2;`
	`12`	`+privatestaticint[]arr;`
	`13`	`+`
	`14`	`+@BeforeClass`
	`15`	`+publicstaticvoidsetup() {`
	`16`	`+solution1 =new_1539.Solution1();`
	`17`	`+solution2 =new_1539.Solution2();`
	`18`	`+ }`
	`19`	`+`
	`20`	`+@Test`
	`21`	`+publicvoidtest1() {`
	`22`	`+arr =newint[]{2,3,4,7,11};`
	`23`	`+assertEquals(9,solution1.findKthPositive(arr,5));`
	`24`	`+ }`
	`25`	`+`
	`26`	`+@Test`
	`27`	`+publicvoidtest2() {`
	`28`	`+arr =newint[]{1,2,3,4};`
	`29`	`+assertEquals(6,solution1.findKthPositive(arr,2));`
	`30`	`+ }`
	`31`	`+`
	`32`	`+@Test`
	`33`	`+publicvoidtest3() {`
	`34`	`+arr =newint[]{2,3,4,7,11};`
	`35`	`+assertEquals(9,solution2.findKthPositive(arr,5));`
	`36`	`+ }`
	`37`	`+`
	`38`	`+@Test`
	`39`	`+publicvoidtest4() {`
	`40`	`+arr =newint[]{1,2,3,4};`
	`41`	`+assertEquals(6,solution2.findKthPositive(arr,2));`
	`42`	`+ }`
	`43`	`+`
	`44`	`+}`

Comments

(0)