我们得到了一个整数数组,我们需要找到最小子段的大小,这样在删除它之后数组中的所有元素都是不同的。如何使用 O(nlogn )?我尝试阅读各种使用二进制搜索的提交,但我无法理解它们。
我的尝试 - 我使用蛮力在 n^2logn 中解决了这个问题,但我想知道如何应用二进制搜索来解决 O(nlogn) 中的这个问题。
问题链接 - https://codeforces.com/contest/1208/problem/B
实现二分查找的解决方案之一的链接 - https://codeforces.com/contest/1208/submission/59494540
最佳答案
在链接的解决方案中,如果可以通过删除大小为 siz
的子数组使所有数字唯一,则函数 check(int siz)
返回 true。它在 O(n) 时间内完成。
因为 check(x) == true
意味着 check(y) == true
对于所有 y >= x
,main()
函数可以做二分查找找到siz
的最小值使得check(siz) == true
,这就是解决方案问题。
如果 check(mid) == true
,则答案不大于 mid
。如果 check(mid) == false
,则答案大于 mid
。
二分搜索需要 O(log n) 次检查
的评估,总共 O(n log n) 次。 p>
关于algorithm - 如何使用二进制搜索解决以下问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57727473/