LeetCode:658. 找到 K 个最接近的元素 - Python

这篇具有很好参考价值的文章主要介绍了LeetCode:658. 找到 K 个最接近的元素 - Python。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

658. 找到 K 个最接近的元素

问题描述:

给定一个 排序好 的数组 arr ,两个整数 kx ,从数组中找到最靠近 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 <= 10^4
  • arr 按 升序 排列
  • -10^4 <= arr[i], x <= 10^4

问题分析:

这个题目解法很多,现在咱们介绍一种最常见的方法,二分查找,然后左右扩展的方式:
(1)使用二分查找法,找到目标元素x插入位置right
(2)确定左右最初始边界:left = right - 1right
(3)根据 x - arr[left] 和 arr[right] - x 值的大小关系,进行左右扩展即可(左边大,就向右边扩展)。

Python3实现:

# @Time   :2023/09/13
# @Author :Liu
class Solution:

    def searchInsert(self, nums: List[int], target: int) -> int:  # 找插入位置

        lift, right = 0, len(nums) - 1
        res = len(nums)

        while lift <= right:
            mid = (lift + right) // 2
            if nums[mid] >= target:
                right = mid - 1
                res = mid
            else:
                lift = mid + 1
        return res

    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
    	# import bisect
        # right = bisect.bisect_left(arr, x)
        right = self.searchInsert(arr, x)  # 插入的位置
        
        left = right - 1
        for _ in range(k):  # 扩展
            if left < 0:
                right += 1
            elif right >= len(arr) or x - arr[left] <= arr[right] - x:
                left -= 1
            else:
                right += 1
        return arr[left + 1: right]

相关参考:
[1]LeetCode:658. 找到 K 个最接近的元素
声明: 总结学习,有问题或不当之处,可以批评指正哦,谢谢。文章来源地址https://www.toymoban.com/news/detail-712503.html

到了这里,关于LeetCode:658. 找到 K 个最接近的元素 - Python的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 2859.计算 K 置位下标对应元素的和:遍历(附Python一行代码版)

    力扣题目链接:https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/ 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 请你用整数形式返回 nums 中的特定元素之 和 ,这些特定元素满足:其对应下标的二进制表示中恰存在 k 个置位。 整数的二进制表示中的 1 就是这个整

    2024年02月19日
    浏览(35)
  • selenium 要点击的元素被其他元素遮挡 or 无法找到非可视范围内的元素

    selenium 无法找到非可视范围内的元素 org.openqa.selenium.StaleElementReferenceException: The element reference of is stale; either the element is no longer attached to the DOM, it is not in the current frame context, or the document has been refreshed selenium 要点击的元素被其他元素遮挡 org.openqa.selenium.ElementClickInterceptedExce

    2024年02月10日
    浏览(36)
  • 7个最流行的强化学习算法实战案例(附 Python 代码)

    大家好,目前流行的强化学习算法包括 Q-learning、SARSA、DDPG、A2C、PPO、DQN 和 TRPO。 这些算法已被用于在游戏、机器人和决策制定等各种应用中,并且这些流行的算法还在不断发展和改进,本文我们将对其做一个简单的介绍。 技术要学会分享、交流,不建议闭门造车。 本文技

    2024年02月16日
    浏览(49)
  • leetcode997. 找到小镇的法官

    小镇里有 n 个人,按从 1 到 n 的顺序编号。传言称,这些人中有一个暗地里是小镇法官。 如果小镇法官真的存在,那么: 小镇法官不会信任任何人。 每个人(除了小镇法官)都信任这位小镇法官。 只有一个人同时满足属性 1 和属性 2 。 给你一个数组 trust ,其中 trust[i] =

    2023年04月22日
    浏览(78)
  • 华为OD机试 - 计算最接近的数(Java & JS & Python)

    题目描述 给定一个数组X和正整数K,请找出使表达式: X[i] - X[i + 1] -  ... - X[i + K - 1] 结果最接近于数组中位数的下标 i ,如果有多个 i 满足条件,请返回最大的 i. 其中,数组中位数:长度为N的数组,按照元素的值大小升序排列后,下标为 N/2 元素的值 输入描述 无 输出描述

    2024年02月13日
    浏览(45)
  • Leetcode448. 找到所有数组中消失的数字

    题目来源:448. 找到所有数组中消失的数字 set 是一个集合类型的容器,里面的元素具有唯一性,并且所有元素都会根据元素的键值自动被排序,以红黑树为底层数据结构。 我们使用集合set记录nums数组的元素,再遍历set找出找到所有的数组nums中消失的数字。 代码: 结果:

    2024年02月03日
    浏览(44)
  • Selenium入门必备:学会用代码控制浏览器,打开网页、找到元素和退出浏览器

    目录 一、前期准备 1、概述 2、学习目标 3、安装 二、selenium的基本使用 1、加载网页: 2、定位和操作: 3、查看请求信息: 4、退出 小结 三、元素定位的方法 学习目标 1、selenium的定位操作 2、元素的操作 小结 四、selenium的其他操作 学习目标 1、无头浏览器 1、selenium 处理

    2024年02月13日
    浏览(118)
  • Leetcode:【448. 找到所有数组中消失的数字】题解

    题目 给你一个含  n  个整数的数组  nums  ,其中  nums[i]  在区间  [1, n]  内。请你找出所有在  [1, n]  范围内但没有出现在  nums  中的数字,并以数组的形式返回结果。 难度: 简单 题目链接:448. 找到所有数组中消失的数字 示例1 示例2 解题思路: 题目意思是再在有 n

    2024年02月11日
    浏览(40)
  • leetcode--环形链表.找到入环节点(java)

    LeetCode 142:环形链表II 可以在这里测试 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表

    2024年02月07日
    浏览(31)
  • cv2.error: OpenCV(4.9.0) C:\projects\opencv-python\opencv\modules\highgui\src\window.cpp:658: error:

    python使用opencv读取图片没有问题,但是使用imshow的时候报错。 cv2.error: OpenCV(3.4.9) C:projectsopencv-pythonopencvmoduleshighguisrcwindow.cpp:658: error: (-2:Unspecified error) The function is not implemented. Rebuild the library with Windows, GTK+ 2.x or Carbon support. If you are on Ubuntu or Debian, install libgtk2.0-dev and p

    2024年04月11日
    浏览(128)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包