PattySung

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]

<解題一> Time: log(n)


class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0, 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<>();
        for(int i =left ; i <= right; i++){
            res.add(arr[i]);
        }
        return res;
    }
}

Time: O(n) Space: O(n)

<解題二> Binary Tree法 - Time: logn


class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // 初始化左右指針的位置
        int left = 0; // 左指針起始位置
        int right = arr.length - k; // 右指針起始位置，確保可以容納 k 個元素

        // 使用二分搜索來找到最接近 x 的 k 個元素
        while (left < right) {
            int mid = (left + right) / 2; // 計算中間位置

            // 檢查中間位置的元素和 x 的關係
            if (x < arr[mid]) {
                right = mid; // 如果 x 比中間元素小，調整右指針
            } else if (x > arr[mid + k]) {
                left = mid + 1; // 如果 x 比右邊的元素大，調整左指針
            } else {
                // 如果 x 位於中間元素和右邊元素之間，則比較它們與 x 的距離
                if (x - arr[mid] <= arr[mid + k] - x) {
                    right = mid; // 如果左邊元素更接近 x，調整右指針
                } else {
                    left = mid + 1; // 如果右邊元素更接近 x，調整左指針
                }
            }
        }

        // 構建結果列表
        List<Integer> res = new ArrayList<>(k);
        for (int i = left; i < left + k; i++) {
            res.add(arr[i]);
        }

        return res; // 返回包含最接近 x 的 k 個元素的列表
    }
}

Time: O(log(n) + k) Space: O(k)

Leetcode-658. Find K Closest Elements

<解題一> Time: log(n)

<解題二> Binary Tree法 - Time: logn