658. Find K Closest Elements - Medium

前往題目

想法

• 因為是sorted，所以應該可以用binary search快速定位

思路

這題有sliding window和結合了binary search的sliding window兩種解法，但我在評論區看到的binary search解法，無法理解其中一兩行code，所以選擇sliding window

1. 左右兩個指針，頭與尾
2. 每次計算左邊以及右邊到x的距離
3. 相等或右邊比較大的時候就往左移(因為距離相同是取index較小的那一方)，直到這個window小於k了
4. 取得sliding window裡所有的數字就是答案

Code

Sliding window解答

綜合Binary search解答

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

        List<Integer> res = new ArrayList<>();
        
        // Keep shrinking the size
        while (right - left >= k) {
            int distLeft = Math.abs(arr[left] - x);
            int distRight = Math.abs(arr[right] - x);

            // When equals, use the smaller index
            if (distLeft <= distRight) {
                --right;
            } else {
                ++left;
            }
        }

        // Add all the numbers within the range
        while (left <= right) {
            res.add(arr[left]);
            ++left;
        }
        return res;
    }
}

2024/05/01

• 想得太複雜，本來想用heap+binary search+sliding window

2024/07/15

• 少了絕對值