Python Simple, O(n) Solution


  • 1
    D
        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]

  • 0

    (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).


  • 0
    D

    ah good point


  • 0

    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).


Log in to reply
 

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