The question

Give A target number, A non-negative integer k, and an array A sorted in ascending order. Find k integers in A that are closest to target. Return the k number and sort it in ascending order of proximity to target, with the smaller number first if they are equally close.

Matters needing attention

The value k is a non-negative integer and will always be smaller than the length of the sorted array.

Length of the given array is positive and will not exceed 10^4

Absolute value of elements in the array and x will not exceed 10^4

The sample

If A = [1, 2, 3], target = 2 and k = 3, then return [2, 1, 3].

If A = [1, 4, 6, 8], target = 3 and k = 3, then return [4, 1, 6].

Train of thought

The general solution to this problem is easy to figure out, but violence works wonders, and we’re just going to say the optimal solution, which is order logn plus k in time.

So the point of this problem is that array A is ordered, so as long as it’s ordered, you can think about dichotomy.

We find the number closest to target by dividing A. After finding the number, we use the idea of double Pointers to spread from the number found to both sides successively until the number k is satisfied.

The idea is simple, pay attention to the judgment of some boundary conditions in the coding process.

code

class Solution:
    """
    @param A: an integer array
    @param target: An integer
    @param k: An integer
    @return: an integer array
    """
    def kClosestNumbers(self, A, target, k):
        if k == 0:
            return []
        if not A:
            return []
        lp = None
        rp = None
        start = 0
        end = len(A) - 1
        while start + 1 < end:
            mid = int(start + (end - start) / 2)
            if A[mid] == target:
                start = mid
                end = mid + 1
                break
            elif A[mid] < target:
                start = mid
            else:
                end = mid
        if abs(A[start] - target) <= abs(A[start] - target):
            lp = start
            rp = end
        else:
            lp = end
            rp = end + 1
        cnt = 0
        ans = list()
        while cnt < k:
            cnt += 1
            if lp < 0 and rp >= len(A):
                return []
            elif lp < 0:
                ans.append(A[rp])
                rp += 1
            elif rp >= len(A):
                ans.append(A[lp])
                lp -= 1
            elif abs(A[lp] - target) <= abs(A[rp] - target):
                ans.append(A[lp])
                lp -= 1
            else:
                ans.append(A[rp])
                rp += 1
        return ans
Copy the code