def findClosestElements(self, arr, k, x): end = k for i in xrange(k, len(arr)): delta = abs(arr[i] - x) - abs(arr[i - k] - x) if delta > 0: return arr[end - k:end] if delta < 0: end = i + 1 return arr[end - k:end]
(Edit: This refers to the original title, which said "O(n-k)". It's fixed now.)
@dylan20 It's not O(n-k). In case of k=n, that would mean O(0). But your
arr[end - k:end] copies the entire array, which takes Θ(n).
Hmm, I just realized that I didn't even need to look at the special cases with k=n. I did because the
arr[end - k:end] alone already disproved O(n-k), and I'm rather minimalistic. But if we look at the whole code, we can simply say that the loop takes Θ(n-k) and the return value takes Θ(k), for a total of Θ(n).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.