leetcode 658. Find K Closest Elements | 658. 找到 K 个最接近的元素（二分查找+双指针）

淡淡的烟草味﹌ 2022-10-12 01:40 132阅读 0赞

## 题目 ##

[https://leetcode.com/problems/find-k-closest-elements/][https_leetcode.com_problems_find-k-closest-elements]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

在arr中找到第一个小于等于x的位置mid，然后再根据题意，用双指针分别向左、向右移动。

优化点：最后只要有两个边界，就可以 subString 之后用来返回了，不需要每一个元素都 add 到双端队列中。

class Solution { 
        public List<Integer> findClosestElements(int[] arr, int k, int x) { 
            // 在arr中找到第一个小于等于x的位置mid
            int l = 0;
            int r = arr.length - 1;
            int mid = l + r / 2;
            while (l < mid) { 
                if (arr[mid] == x) break;
                else if (arr[mid] < x) l = mid;// 保左边界
                else r = mid - 1;
                mid = (l + r) / 2;
            }
            // 从mid开始 双指针分别左右移动
            l = mid;
            r = Math.min(mid + 1, arr.length);
            Deque<Integer> q = new LinkedList<>();
            while (q.size() < k) { 
                if (l < 0) q.addLast(arr[r++]);
                else if (r > arr.length - 1) q.addFirst(arr[l--]);
                else { 
                    if (arr[l] == arr[r] || x - arr[l] <= arr[r] - x) q.addFirst(arr[l--]);
                    else q.addLast(arr[r++]);
                }
            }
            return new ArrayList<>(q);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_find-k-closest-elements]: https://leetcode.com/problems/find-k-closest-elements/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/1b23c41a821c425ea718ad7cf0e9b212.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/07d938290e7f4337a89ef0aae8b62eec.png