在O（nlogn）和O（logn）附加空间中求最小正数
这是一个众所周知的问题的略微修改版本，但我似乎无法理解这一点。
我们得到一个大小为n的数组，它包含无序的正数序列，没有重复项。我试图找到数组中未包含的最小正数，但我无法以任何方式对数组进行排序或编辑。整个过程应该是O（nlogn）时间和O（logn）空间的复杂性。
我能想到的所有解都是多项式时间复杂度的。
共有1个答案
您可以通过对答案进行二进制搜索来解决这个问题，而无需修改数组。请记住，我们正在寻找不在数组中的最小正整数。这意味着答案不能大于n 1，因为数组中只有n个数字。所以我们只需要在1和n 1之间进行二进制搜索来找到答案。
在我们的二进制搜索中，我们想回答这个问题：对于给定的数字k，每个整数1到k都包含在我们的数组中吗？因为没有重复项，我们可以通过计算数组中小于或等于k的元素数来解决这个问题。如果计数为k，则每个这样的整数都在我们的数组中；否则，至少缺少一个。
所以我们二进制搜索找到k的最小值，其中上述属性为假。二进制搜索需要O（log n）次迭代，每次迭代总共需要O（n log n）时间。空间实际上是O（1），因为我们只需要一个用于计数的变量。
-
我们被要求创建一个在O（logn）中最坏情况下运行的算法 该算法由3个函数组成：
-
就像谷歌地图一样，给定一百万个经纬度坐标列表，你将如何打印距离给定位置最近的k个城市？ 我在一次面试中问了这个问题。面试官说这可以在O（n）中通过使用插入排序到k来完成，而不是对整个列表进行排序，即NlogN。我在网上找到了其他答案，大多数人都说NLogN...他[面试官]正确吗？
-
给定一个二叉树，我想返回最大和子树的根。 最大子树：树的子树，其所有节点的总和大于任何其他子树的总和。 编辑：节点值为整数。 我可以做以下需要O（n^2）的事情。 计算左子树中所有节点的总和 计算右子树中所有节点的总和 如果左子树和右子树的和以及根的值大于当前最大和，则根存储在结果中 以左子树作为根递归调用此函数 以右子树作为根递归调用此函数。这将需要O（n^2） 我可以将其更改为自底向上的方法，
-
问题内容： Go内置函数的复杂性是什么？字符串串联使用呢？ 我想通过附加两个切片（不包括该元素）从切片中删除一个元素。http://play.golang.org/p/RIR5fXq- Sf http://golang.org/pkg/builtin/#append表示，如果目的地有足够的容量，则该分片为。我希望“切片”是一个恒定时间的操作。我也希望同样适用于使用的字符串连接。 问题答案： 所有这
-
输入数组只有1和-1，算法将找到一个和为0的子数组。 输入={1,1,-1,1,-1,-1,-1,-1} 输出=1,8（1是起始索引，8是最后索引） 唯一的约束是算法不能使用任何辅助数据结构。在这个约束条件下，解决方案必须是最有效的。此外，还允许使用递归。