0658. Find K Closest Elements - kumaeki/LeetCode GitHub Wiki

0658. Find K Closest Elements


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 <= 104
  • arr is sorted in ascending order.
  • -104 <= arr[i], x <= 104

解法1

用binarySearch 找到离x最近的数, 然后循环比较left和right两边的值,总是把差值较小的放入结果集中.

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int index = Arrays.binarySearch(arr, x);
        if(index < 0)
            index = -index - 1;
        
        LinkedList<Integer> result = new LinkedList<Integer>();

        int left = index - 1, right = index;
        while(result.size() < k){
            if(left < 0)
                result.addLast(arr[right++]);
            else if(right >= arr.length)
                result.addFirst(arr[left--]);
            else{
                int difl = x - arr[left], difr = arr[right] - x;
                if(difl <= difr)
                    result.addFirst(arr[left--]);
                else
                    result.addLast(arr[right++]);
            }
        }
        
        return result;
        
    }
}
⚠️ **GitHub.com Fallback** ⚠️