K Closest Numbers In Sorted Array(Ladder)

Description

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.

Example:
Given A = [1, 2, 3], target = 2 and k = 3, return [2, 1, 3].
Given A = [1, 4, 6, 8], target = 3 and k = 3, return [4, 1, 6].

Challenge:
O(logn + k) time complexity.

Link

Lintcode_ladder

Method

1. Binary Search
2. x

Example

1. 1

   class Solution {
   public:
    /**
     * @param A an integer array
     * @param target an integer
     * @param k a non-negative integer
     * @return an integer array
     */
    vector<int> kClosestNumbers(vector<int>& nums, int target, int k) {
        // Write your code here
        if (nums.empty()) {
            return {};
        }
        vector<int> result;
        int pos = -1;
        int start = 0;
        int end = nums.size()-1;
        while (start+1 <end) {
            int mid = start + (end-start)/2;
            if (target <=nums[mid]) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (target <=nums[start]) {
            pos = start;
        } else if (target <= nums[end]) {
            pos = end;
        } else {
            pos = nums.size();
        }
        // find pair
        int left = pos-1;
        int right = pos;
        for (int i = 0; i < k; ++i) {
            if (left < 0) {
                result.push_back(nums[right++]);
            } else if (right >= nums.size()) {
                result.push_back(nums[left--]);
            } else {
                if (target - nums[left] <= nums[right] - target) {
                    result.push_back(nums[left--]);
                } else {
                    result.push_back(nums[right++]);
                }
            }
        }
        return result;
    }
   };
   

Similar problems

x

Tags

x