CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

    • 双指针法理论基础
    • 左右指针

      • 验证回文串
      • 最多删除一个字符得到回文
      • 回文子字符串的个数
      • 反转字符串
      • 反转字符串II
      • 两数之和 II - 输入有序数组
      • 反转字符串中的单词 III
      • 翻转字符串里的单词
      • 剑指 Offer 58 - II. 左旋转字符串
      • 有序数组的平方
      • 三数之和
      • 四数之和
      • 删除排序链表中的重复元素
      • 删除排序链表中的重复元素 II
      • 删除有序数组中的重复项
      • 压缩字符串
      • 移除元素
      • 移动零
      • 调整数组顺序使奇数位于偶数前面
      • 最短无序连续子数组
      • 找到 K 个最接近的元素
        • 📃 题目描述
        • 🔔 解题思路
        • 💥 复杂度分析
      • 盛最多水的容器
    • 滑动窗口

    • 快慢指针

    • 其他

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 双指针法
  • 左右指针
小牛肉
2022-08-26
目录

找到 K 个最接近的元素

# 📃 题目描述

题目链接:658. 找到 K 个最接近的元素 (opens new window)

# 🔔 解题思路

美团一面的原题,一开始想的暴力排序,后来面试官引导了很久才想出来二分查找 + 双指针

二分查找到 x 的位置(注意这里 x 可能不存在于 arr 中),然后左右指针找 k 个最接近 x 的数

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list = new ArrayList<>();

        int index = getX(arr, x);

        // 这里【不】应该初始化为 left = index, right = index + 1
        // ex: [0,0,1,2,3,3,4,7,7,8] k = 3, x = 5
        int left = index - 1, index;
        while (k != 0 && (left >= 0 || right < arr.length)) {
            int l = (left >= 0) ? Math.abs(arr[left] - x) : Integer.MAX_VALUE;
            int r = (right < arr.length) ? Math.abs(arr[right] - x) : Integer.MAX_VALUE;

            if (l <= r) {
                left --;
            }
            else {
                right ++;
            }

            k --;
        }

        for (int i = left + 1; i <= right - 1; i ++) {
            list.add(arr[i]);
        }

        return list;
    }

    // 找到 x 的下标,如果 x 不存在,返回第一个比 x 大的元素的下标
    private int getX(int[] arr, int x) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] == x) {
                return mid;
            }
            else if (arr[mid] > x) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        return left;
    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
最短无序连续子数组
盛最多水的容器

← 最短无序连续子数组 盛最多水的容器→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式