Commit5c2d9e0

authored

Create 1481-least-number-of-unique-integers-after-k-removals.kt

1 parentf454ab4 commit5c2d9e0Copy full SHA for 5c2d9e0

File tree

+58

-0

lines changed

+58

-0

lines changed

Lines changed: 58 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,58 @@`
	`1`	`+// Use of buckets`
	`2`	`+classSolution {`
	`3`	`+funfindLeastNumOfUniqueInts(arr:IntArray,k:Int):Int {`
	`4`	`+val n= arr.size`
	`5`	`+val counts=HashMap<Int,Int> ()`
	`6`	`+val buckets=HashMap<Int,Int> ()`
	`7`	`+`
	`8`	`+ arr.forEach { n->`
	`9`	`+ counts[n]= (counts[n]?:0)+1`
	`10`	`+ }`
	`11`	`+`
	`12`	`+ counts.values.forEach { count->`
	`13`	`+ buckets[count]= (buckets[count]?:0)+1`
	`14`	`+ }`
	`15`	`+`
	`16`	`+var k= k`
	`17`	`+var res= counts.size`
	`18`	`+for (nin1 until buckets.size) {`
	`19`	`+var remove= buckets[n]?:0`
	`20`	`+val total= n* remove`
	`21`	`+if (k>= total) {`
	`22`	`+ k-= total`
	`23`	`+ res-= remove`
	`24`	`+ }else {`
	`25`	`+ remove= k/ n`
	`26`	`+ res-= remove`
	`27`	`+break`
	`28`	`+ }`
	`29`	`+ }`
	`30`	`+`
	`31`	`+return res`
	`32`	`+ }`
	`33`	`+}`
	`34`	`+`
	`35`	`+// Use a heap`
	`36`	`+classSolution {`
	`37`	`+funfindLeastNumOfUniqueInts(arr:IntArray,k:Int):Int {`
	`38`	`+val freq=HashMap<Int,Int> ()`
	`39`	`+ arr.forEach { n->`
	`40`	`+ freq[n]= (freq[n]?:0)+1`
	`41`	`+ }`
	`42`	`+`
	`43`	`+val heap=PriorityQueue<Int> { a, b-> a- b }`
	`44`	`+ heap.addAll(freq.values)`
	`45`	`+`
	`46`	`+var k= k`
	`47`	`+var res= heap.size`
	`48`	`+while (k>0&& heap.isNotEmpty()) {`
	`49`	`+val f= heap.poll()`
	`50`	`+if (k>= f) {`
	`51`	`+ k-= f`
	`52`	`+ res-=1`
	`53`	`+ }`
	`54`	`+ }`
	`55`	`+`
	`56`	`+return res`
	`57`	`+ }`
	`58`	`+}`

Comments

(0)