尊享面试100(272.最接近的二叉树搜索值|| python)

ops/2024/12/12 6:39:01/

刚开始想着用最小堆,把每个元素都加进去,然后找出最小的k个值,复杂度应该是(n+klogn)

python">import heapq as pq
class Solution:def __init__(self):self.h = []pq.heapify(self.h)def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:if not root: returnself.target = targetself.dfs(root)ans = []for i in range(k):ans.append(pq.heappop(self.h)[1])return ansdef dfs(self, root):if not root: returnpq.heappush(self.h, [abs(self.target - root.val), root.val])self.dfs(root.left)self.dfs(root.right)

题目要求在(n)的复杂度下解决。

终于发现,题目给的是二叉搜索树,特点是:左子节点<当前节点<右子节点

那思路就来了:

1.把所有节点都放在列表ls中

2.找到第一个大于target的值

3.双指针,一个指针向左走,一个指针向右转,距离target最小的节点的值保留。

python">class Solution:def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:if not root: returnself.ls = []self.dfs(root)leth = len(self.ls)l, r = 0, leth - 1while l < r:mid = l + r >> 1if self.ls[mid] < target:l = mid + 1else:r = midl, r = l-1, lans = []while k and l >= 0 and r < leth:n1 = abs(self.ls[l] - target)n2 = abs(self.ls[r] - target)if n1 <= n2:ans.append(self.ls[l])l -= 1else:ans.append(self.ls[r])r += 1k -= 1if k > 0:if l < 0: ans += self.ls[r:r+k]else: ans += self.ls[l-k+1:l+1]return ansdef dfs(self, root):if not root: returnself.dfs(root.left)self.ls.append(root.val)self.dfs(root.right)

复杂度为(n+logn+k),四舍五入满足题目的条件。


http://www.ppmy.cn/ops/38548.html

相关文章

hbase建表预分区的2种方法

以下案例建表并设置预分区,分别测试以下2种方法 1.固定散列 示例:rowkey以日期为前缀 create ‘test’,‘cf1’, SPLITS > [‘202401’, ‘202402’, ‘202403’] put ‘test’,‘20240101’,‘cf1:name’,‘20240101’ put ‘test’,‘20240102’,‘cf1:name’,‘2024010…

redisson 使用脚本实现判断元素不在队列中则插入的原子操作

脚本逻辑&#xff1a; 取出队列所有元素遍历元素查找值是否存在不存在则推入 final String scriptText """local valuesInTarget redis.call(lrange, KEYS[1], 0, -1);local index 0;for i, v in ipairs(valuesInTarget) doif v value thenindex ibreake…

通过Docker Compose部署GitLab和GitLab Runner(一)

GitLab 是一个用于版本控制、项目管理和持续集成的开源软件平台&#xff0c;它提供了一整套工具&#xff0c;能够帮助团队高效地协作开发。而 GitLab Runner 则是 GitLab CI/CD 的执行者&#xff0c;用于运行持续集成和持续交付任务。 在本文中&#xff0c;我们将使用 Docker …

双网口扩展IO支持8DO输出

M320E以太网远程I/O数据采集模块是一款工业级、隔离设计、高可靠性、高稳定性和高精度数据采集模块&#xff0c;嵌入式32位高性能微处理器MCU&#xff0c;集成2路工业10/100M自适应以太网模块里面。提供多种I/O&#xff0c;支持标准Modbus TCP&#xff0c;可集成到SCADA、OPC服…

鲁棒性能优化问题

鲁棒性能优化问题是一类基于不确定性和干扰的优化问题。鲁棒优化是一种在内部结构和外部环境不确定环境下进行优化的新方法。其核心思想是在考虑参数的不确定性或外部环境的扰动时&#xff0c;寻找一个最优解&#xff0c;该解在所有可能的情况下都能保持较好的性能。 鲁棒优化…

掌握Android Fragment开发之魂:Fragment的深度解析(下)

在上一篇文章中&#xff0c;我们深入探讨了Fragment 通信&#xff0c;包含Fragment 向 Activity 传递数据、Activity 向 Fragment 传递数据、Fragment 之间的通信方式。感兴趣的朋友&#xff0c;请前往查阅&#xff1a; 掌握Android Fragment开发之魂&#xff1a;Fragment的深度…

安装oh-my-zsh(命令行工具)

文章目录 一、安装zsh、git、wget二、安装运行脚本1、curl/wget下载2、手动下载 三、切换主题1、编辑配置文件2、切换主题 四、安装插件1、zsh-syntax-highlighting&#xff08;高亮语法错误&#xff09;2、zsh-autosuggestions&#xff08;自动补全&#xff09; 五、更多优化配…

数据的输入和输出

早期的总线系统 为了解决通信的问题、主板上铺设了一条公共线路、各个设备都连接到这条线路上、不管谁要和谁通信、都能使用它来传输、这条线路就是总线。 总线上有CPU、内存、鼠标、键盘、硬盘、网卡、声卡、显卡等… 说是一条总线、实际上是包含了传输数据的数据总线、传输…