Daily LeetCode – day0027 0658. Find K Closest Elements

// 0658. Find K Closest Elements
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int right = arr.length - 1;
        int middle = 0;
        while (left + 1 < right) {
            middle = (left + right) / 2;
            if (arr[middle] == x) {
                left = middle;
                right = middle;
                break;
            } else if (arr[middle] > x) {
                right = middle;
            } else {
                left = middle;
            }
        }
        if (left != right) {
            if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
                middle = right;
            } else {
                middle = left;
            }
        }
        List<Integer> ans = new ArrayList<>();
        ans.add(arr[middle]);
        left = middle - 1;
        right = middle + 1;
        while (ans.size() < k) {
            if (left < 0) {
                ans.add(arr[right]);
                ++right;
            } else if (right >= arr.length) {
                ans.add((arr[left]));
                --left;
            } else if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
                ans.add(arr[right]);
                ++right;
            } else {
                ans.add((arr[left]));
                --left;
            }
        }
        ans.sort((Integer i1, Integer i2) -> (i1 - i2));
        return ans;
    }
}
学习笔记:
这道题是二分法的题目。
我先用二分法找到了最接近的元素,然后再往两头扩展一个个加进去。
没想到速度那么慢,用了11ms,比很多人都慢。
但我看快的方法也都差不多,只不过是指针往两边跑,最后把元素加入ans里面。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。