O(log n) in 1 line Go


  • 1

    Here I implemented my O(log(n) + k) solution in Go, to get rid of the k in the complexity (because due to how Go's slices work, arr[i:i+k] only takes O(1) time).

    func findClosestElements(arr []int, k int, x int) []int {
    	i := sort.Search(len(arr) - k, func(i int) bool { return x - arr[i] <= arr[i+k] - x })
    	return arr[i:i+k]
    }
    

    Oneliner version by slicing twice:

    func findClosestElements(arr []int, k int, x int) []int {
    	return arr[sort.Search(len(arr) - k, func(i int) bool { return x - arr[i] <= arr[i+k] - x }):][:k]
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.