CodeSignal 一道 OA 题 -- 如何优化? 红黑树？

这题暴力解会超时。楼主想了半天感觉可以用 balanced binary search tree 来做，使得查找的时间复杂度降低到 O(logN)，不过能力有限，不知道怎么在 Java 中实现，难道要徒手实现一个红黑

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

10^9.

补充内容 (2023-01-08 02:12 +8:00):
顺便求点大米T-T

匿名用户 发表于 2023-01-07 10:12:41
TreeSet 搜索时会超时

不可能诶 这题如果treeset超时 那其他的bit 或者segment tree也都超时啊

看起来似乎坐标一定是整数而且应该range不是特别大的样子，那你直接用树状数组(Binary Indexed Tree)就行，如果[x:x+size]区间和是0就return 1。
如果range比较大可以离散化一下。
只有坐标是浮点数的时候才一定要用bst，这种情况下应该只有python是没有内置数据结构的，java应该有个treemap可以用。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

匿名用户 发表于 2023-1-4 13:54
感谢回复！看来还得去学学这个 Binary Indexed Tree 数据结构。不知道能否用线段树 segment tree 来解决 ...

树状数组就是简化版只能求区间和的线段树，面试的时间感觉写线段树有点来不急。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这题用个treeset就写了诶

1: 插入一个点到treeset

2 有没有在start 和 end之间的元素

匿名用户 发表于 2023-1-7 06:09
这题用个treeset就写了诶

1: 插入一个点到treeset

TreeSet 搜索时会超时