Commitb562f75

authored

Update 0658-find-k-closest-elements.kt (Optimization)

Added solution using binary search instead of linear. Both solutions are in the file.

1 parent037a70d commitb562f75Copy full SHA for b562f75

File tree

+23

-0

lines changed

+23

-0

lines changed

Lines changed: 23 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,3 +1,26 @@`
	`1`	`+/*`
	`2`	`+* Optimized solution with binary search for the k-window instead of linear search. Time O(LogN-K) and Space O(1)`
	`3`	`+*/`
	`4`	`+classSolution {`
	`5`	`+funfindClosestElements(arr:IntArray,k:Int,x:Int):List<Int> {`
	`6`	`+`
	`7`	`+var left=0`
	`8`	`+var right= arr.size- k`
	`9`	`+`
	`10`	`+while (left< right) {`
	`11`	`+val mid= (left+ right)/2`
	`12`	`+if (x- arr[mid]> arr[mid+ k]- x)`
	`13`	`+ left= mid+1`
	`14`	`+else`
	`15`	`+ right= mid`
	`16`	`+ }`
	`17`	`+`
	`18`	`+val res=ArrayList<Int>()`
	`19`	`+for(iin left until right+k) res.add(arr[i])`
	`20`	`+return res`
	`21`	`+ }`
	`22`	`+}`
	`23`	`+`
`1`	`24`	`/*`
`2`	`25`	`* Linear search with window resizing. Time: O(N-K) and Space O(1)`
`3`	`26`	`*/`

Comments

(0)