658. Find K Closest Elements

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

• |a - x| < |b - x|, or
• |a - x| == |b - x| and a < b

Example 1:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Example 2:

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

Constraints:

• 1 <= k <= arr.length
• $1 <= arr.length <= 10^4$
• arr is sorted in ascending order.
• $-10^4 <= arr[i], x <= 10^4$

Code

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int right = arr.length - k;

        while (left < right) {
            int mid = (left + right) / 2;

            if(x < arr[mid]) {
                right = mid;
            } else if (x > arr[mid + k]) {
                left = mid + 1;
            } else {
                if(x - arr[mid] <= arr[mid + k] - x) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
        }

        List<Integer> res = new ArrayList<>(k);
        for (int i = left; i < left + k; i++) {
            res.add(arr[i]);
        }

        return res;
    }
}

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int right = arr.length - 1;

        while (right - left >= k) {
            if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
                left++;
            } else {
                right--;
            }
        }

        List<Integer> res = new ArrayList<>(k);
        for (int i = left; i <= right; i++) {
            res.add(arr[i]);
        }

        return res;
    }
}