LeetCode_排序_二分搜索_双指针_中等_658.找到 K 个最接近的元素

﹏ヽ暗。殇╰゛Y 2023-10-06 23:58 1阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

*  |a - x| < |b - x| 或者
 *  |a - x| == |b - x| 且 a < b

**示例 1：**  
输入：arr = \[1,2,3,4,5\], k = 4, x = 3  
输出：\[1,2,3,4\]

**示例 2：**  
输入：arr = \[1,2,3,4,5\], k = 4, x = -1  
输出：\[1,2,3,4\]

**提示：**  
1 <= k <= arr.length  
1 <= arr.length <= 104  
arr 按升序排列  
\-104 <= arr\[i\], x <= 104

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/find-k-closest-elements

## 2.思路 ##

（1）排序  
首先将数组 arr 按照题目中更接近的定义进行排序，即越接近 x 的数越排在前面。排序之后的前 k 个数即为 k 个最接近 x 的元素，此时将这 k 个元素进行升序排序后再直接返回即可。

（2）二分搜索 & 双指针  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————排序
    class Solution {
        
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
        
            List<Integer> arrList = new ArrayList<>();
            for (int num : arr) {
        
                arrList.add(num);
            }
            arrList.sort((a, b) -> {
        
                //按照题目中更接近 x 的定于对 arrList 中的数进行排序
                if (Math.abs(a - x) != (Math.abs(b - x))) {
        
                    return Math.abs(a - x) - Math.abs(b - x);
                } else {
        
                    return a - b;
                }
            });
            // arrList 中的前 k 个数即为 k 个最接近 x 的元素
            List<Integer> res = arrList.subList(0, k);
            // 对 res 进行升序排序
            Collections.sort(res);
            return res;
        }
    }

//思路2————二分搜索 & 双指针
    class Solution {
        
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
        
            int right = leftBoundSearch(arr, x);
            int left = right - 1;
            while (k-- > 0) {
        
                if (left < 0) {
        
                    right++;
                } else if (right >= arr.length) {
        
                    left--;
                } else if (x - arr[left] <= arr[right] - x) {
        
                    left--;
                } else {
        
                    right++;
                }
            }
            List<Integer> res = new ArrayList<>();
            for (int i = left + 1; i < right; i++) {
        
                res.add(arr[i]);
            }
            return res;
        }
        
        //查找 target 在数组 arr 中的最左边界
        public int leftBoundSearch(int[] arr, int target) {
        
            int left = 0;
            int right = arr.length - 1;
            while (left <= right) {
        
                int mid = left + (right - left) / 2;
                if (arr[mid] < target) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
            return left;
        }
    }

[Link 1]: https://leetcode.cn/problems/find-k-closest-elements/solution/zhao-dao-k-ge-zui-jie-jin-de-yuan-su-by-ekwtd/