狗家大概挂经

不在力扣里
有一个黑盒function叫做run()，输入是一些testcases。现在给你一个testcase l

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

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

:15 +08:00):
update 并非挂经

匿名用户 发表于 2026-1-18 13:11
假设 test list [1, 2, 3, .... , n]

那么首先最多run n次找到第一个fail test case： run([1, 2, 3, .. ...

考虑run是线性复杂度的，这个第一步就会O(n^2)了

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

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

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

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

积分不够能不能再发下啊 这个是r1吗 谢谢

匿名用户 发表于 2026-1-15 22:12
积分不够能不能再发下啊 这个是r1吗 谢谢

不是很懂积分机制。可以看这个帖子 https://leetcode.com/discuss/pos ... ind-pair-by-a-rt9t/

logn times of run, 这个solution 不对吗？

非悱啡 发表于 2026-01-16 08:37:33
logn times of run, 这个solution 不对吗？

在run的复杂度是线性的情况下，整体复杂度，分治能压到O(n)

能麻烦解释一下nlogn的解法吗？

匿名用户 发表于 2026-01-17 21:20:37
chatgpt和上面链接里面讲得应该会比我清楚

假设输入是s，找到中间点mid，跑左边s，再跑右边s，最理想情况就是pair都在左边或者右边，即有一次会f

谢谢。

分治怎么可以压到N?