首页 > 试题广场 >

最接近的K个元素

[编程题]最接近的K个元素
  • 热度指数：556 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的升序数组 nums 和两个整数 k 和 x ，从数组中找到最接近 x (两数之差最小)的 k 个数并升序得输出他们。

整数 a 比整数 b 更接近 x 需要满足
|a-x| < |b-x| ，
|a-x| = |b-x| 时 a < b

数据范围： ，
示例1

输入

[1,2,3,4,5],4,4

输出

[2,3,4,5]
示例2

输入

[1,2,3,4,5],4,3

输出

[1,2,3,4]
示例3

输入

[1,2,3,4],4,0

输出

[1,2,3,4]
算法知识视频讲解
添加回答
Java
xinychan头像 xinychan
import java.util.*;

public class Solution {
    // 所有数据先减x；再取绝对值；得到与x之差的数组，且均为正整数
    // 在x之差的数组中，找到数值最小的数；记录下标
    // 最小值下标为中心，双指针法移动，获取k个数；保存这k个数的下标
    // 对下标进行排序，然后按照下标到 nums 取出数据
    public ArrayList<Integer> closestElement(ArrayList<Integer> nums, int k, int x) {
        // 所有数据先减x；再取绝对值；得到与x之差的数组，且均为正整数
        ArrayList<Integer> absList = new ArrayList<>();
        for (int val : nums) {
            absList.add(Math.abs(val - x));
        }
        // 在x之差的数组中，找到数值最小的数；记录下标
        int minNum = Integer.MAX_VALUE;
        int minIndex = -1;
        int absSize = absList.size();
        for (int i = 0; i < absSize; i++) {
            int val = absList.get(i);
            if (val < minNum) {
                minNum = val;
                minIndex = i;
            }
        }
        // 最小值下标为中心，双指针法移动，获取k个数；保存这k个数的下标
        ArrayList<Integer> idxList = new ArrayList<>();
        // 题目 k>=1；至少要保存一个最小值
        idxList.add(minIndex);
        int times = 0;
        int left = minIndex - 1;
        int right = minIndex + 1;
        // 已经保存过了 minIndex，保存的下标需要减1
        while (times < k - 1) {
            if (left < 0) {
                // left 下标小于0时，移动 right 下标
                idxList.add(right);
                right++;
            } else if (right >= absSize) {
                // right 下标小于列表长度，移动 left 下标
                idxList.add(left);
                left--;
            } else {
                // left/right 在列表长度之内，计算与X之差的大小；那个小就保存下标
                if (absList.get(left) <= absList.get(right)) {
                    idxList.add(left);
                    left--;
                } else {
                    idxList.add(right);
                    right++;
                }
            }
            times++;
        }
        // 对下标列表排序，获取升序后的下标
        Collections.sort(idxList);
        // 依据下标获取 nums 源数据
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < idxList.size(); i++) {
            int index = idxList.get(i);
            int val = nums.get(index);
            result.add(val);
        }
        return result;
    }
}
发表于 2022-12-13 01:04:07 回复(0)
提交观点

问题信息

二分 排序 双指针
难度：
1条回答 1803浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号