Commit99d368e

committed

add a solution for 347

1 parentcdabae0 commit99d368eCopy full SHA for 99d368e

File tree

+34

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _347.java
- test/java/com/fishercoder
  - _347Test.java

+34

-0

lines changed

Lines changed: 31 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -7,6 +7,7 @@`
`7`	`7`	`importjava.util.Map.Entry;`
`8`	`8`	`importjava.util.PriorityQueue;`
`9`	`9`	`importjava.util.Queue;`
	`10`	`+importjava.util.TreeMap;`
`10`	`11`
`11`	`12`	`publicclass_347 {`
`12`	`13`
`@@ -74,4 +75,34 @@ public int[] topKFrequent(int[] nums, int k) {`
`74`	`75`	`returnarr;`
`75`	`76`	`}`
`76`	`77`	`}`
	`78`	`+`
	`79`	`+publicstaticclassSolution3 {`
	`80`	`+/**`
	`81`	`+ * Use hashtable and heap, it's averaged at 10 ms on Leetocde.`
	`82`	`+ */`
	`83`	`+publicint[]topKFrequent(int[]nums,intk) {`
	`84`	`+Map<Integer,Integer>map =newHashMap<>();`
	`85`	`+for (inti :nums) {`
	`86`	`+map.put(i,map.getOrDefault(i,0) +1);`
	`87`	`+ }`
	`88`	`+TreeMap<Integer,List<Integer>>treeMap =newTreeMap<>((a,b) ->b -a);`
	`89`	`+for (intkey :map.keySet()) {`
	`90`	`+List<Integer>list =treeMap.getOrDefault(map.get(key),newArrayList<>());`
	`91`	`+list.add(key);`
	`92`	`+treeMap.put(map.get(key),list);`
	`93`	`+ }`
	`94`	`+List<Integer>list =newArrayList<>();`
	`95`	`+while (!treeMap.isEmpty()) {`
	`96`	`+list.addAll(treeMap.pollFirstEntry().getValue());`
	`97`	`+if (list.size() ==k) {`
	`98`	`+break;`
	`99`	`+ }`
	`100`	`+ }`
	`101`	`+int[]ans =newint[list.size()];`
	`102`	`+for (inti =0;i <list.size();i++) {`
	`103`	`+ans[i] =list.get(i);`
	`104`	`+ }`
	`105`	`+returnans;`
	`106`	`+ }`
	`107`	`+ }`
`77`	`108`	`}`

Lines changed: 3 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -9,13 +9,15 @@`
`9`	`9`	`publicclass_347Test {`
`10`	`10`	`privatestatic_347.Solution1solution1;`
`11`	`11`	`privatestatic_347.Solution2solution2;`
	`12`	`+privatestatic_347.Solution3solution3;`
`12`	`13`	`privatestaticint[]nums;`
`13`	`14`	`privatestaticint[]expected;`
`14`	`15`
`15`	`16`	`@BeforeClass`
`16`	`17`	`publicstaticvoidsetup() {`
`17`	`18`	`solution1 =new_347.Solution1();`
`18`	`19`	`solution2 =new_347.Solution2();`
	`20`	`+solution3 =new_347.Solution3();`
`19`	`21`	`}`
`20`	`22`
`21`	`23`	`@Test`
`@@ -35,6 +37,7 @@ public void test2() {`
`35`	`37`	`nums =newint[]{3,0,1,0};`
`36`	`38`	`expected =newint[]{0,3};`
`37`	`39`	`assertArrayEquals(expected,solution2.topKFrequent(nums,2));`
	`40`	`+assertArrayEquals(expected,solution3.topKFrequent(nums,2));`
`38`	`41`	`}`
`39`	`42`
`40`	`43`	`@Test`

Comments

(0)