K Closest Numbers In Sorted Array

Given a target number, a non-negative integer k and an integer array A sorted in ascending order, find the k closest numbers to target in A, sorted in ascending order by the difference between the number and target. Otherwise, sorted in ascending order by number if the difference is same.

来源： http://www.lintcode.com/en/problem/k-closest-numbers-in-sorted-array/

分析

先找到最接近的数字，使用Closest Number in Sorted Array中的函数，时间复杂度 O(LogN)

然后从当前位置，使用两个指针：i 和 j。分别向头尾遍历，直到 k 个元素被 add 进结果数组list，

时间复杂度O(min(k, A.length))

public class Solution {
    /**
     * @param A an integer array
     * @param target an integer
     * @param k a non-negative integer
     * @return an integer array
     */
    public int[] kClosestNumbers(int[] A, int target, int k) {
        // Write your code here
        int len = A.length;
        int j = closestNumber(A, target), i = j - 1, di, dj;
         int[] list = new int[Math.min(k, A.length)];
        int count = 0;
        while(len-- != 0 && k-- != 0){
            di = i < 0 ? Integer.MAX_VALUE : A[i] - target;
            dj = j >= A.length ? Integer.MAX_VALUE : A[j] - target;
            if(dj == 0 || Math.abs(dj) < Math.abs(di)){
                list[count++] = A[j++];
            }
            else{
                list[count++] = A[i--];
            }
             
        }
        return list;
    }
     
    private int closestNumber(int[] A, int target) {
        // Write your code here
        if(A == null || A.length == 0)
            return -1;
        int left = 0, right = A.length - 1, mid;
        while(left < right){
            mid = left + (right - left) / 2;
            if(A[mid] < target){
                left = mid + 1;
            }
            else{
                right = mid;
            }
        }
        // when left == right, this is the first position that target can be insert
        if(right > 0 && (A[right] - target) > (target - A[right - 1]))
            return right - 1;
        else
            return right;
    }
}

null